3
$\begingroup$

Good afternoon.

At work I'm currently developing a system which takes user input (well structured) and then stores it in memory to do some processing.

The input is basically a dataset formed by matrix of pxq dimension, with q columns of data and p rows; where each row has the following structure:

n indexes, m attributes, k classes, with $n, m, k \geq 1$

The system can handle inputs from several users at the same time, and the values of n, m, k can be different per dataset. However, no matter which values, there has to be a unique data structure capable of handling the size of the dataset, and store the data in memory efficiently, with a particular emphasis on data reads and inserts, which are the most frequent operations.

I'm currently struggling with two things:

  1. How to describe such structure at a high level (without considering the how it will be stored in memory) using only math equations.
  2. Finding an efficient data structure which can be created previous to the user input. This means, as soon as the text fields are shown to the user, the data structure has to be created and after the user fills every data in the dataset and press Enter the data needs to be inserted (and quickly) into the data structure. However, I don't know if this is entirely possible or if it's the best approach.

I'm open to suggestions. Currently what I have thought of is:

  1. The system takes a dataset $d_{pq}^{nmk}$ as a matrix formed by $p$ rows and $q$ columns.

We define an index $id_{i}, i = 1\ldots n $ as following:

$id_{i} = [a-zA-Z\_][a-zA-Z0-9\_]*$

In an analogous way, it's possible to define an attribute $a_{j}, j = 1\ldots m$ and a class $c_{l}, l = 1\ldots k$:

$a_{j} = [a-zA-Z\_][a-zA-Z0-9\_]*$
$c_{l} = [a-zA-Z\_][a-zA-Z0-9\_]*$

Where each row of a dataset $d_{pq}^{nmk}$ is the union of exactly $n$ indexes, $m$ attributes and $k$ classes, as folowing:

$ID = \bigcup_{i = 1}^{n} id_{i} $

$AT = \bigcup_{j = 1}^{m} a_{j} $

$CL = \bigcup_{l = 1}^{k} c_{l} $

Therefore, a the $t-th$ row of a dataset $d_{pq}^{nmk}$ can be expressed as:

$r_{t} = ID_{t} \bigcup AT_{t} \bigcup CL_{t}$

And thus, a dataset $d_{pq}^{nmk}$ can be expressed in s implified way as:

$d_{pq}^{nmk} = \{r_{t}\}, t = 1\ldots q$

However, I'm not sure if this definition is just enough good as a formal expression of the dataset. Also, I feel it doesn't help to think of a good data structure to handle the dataset (except by a list of lists, of course).

  1. I was thinking the simplest approach would be to define a record with two types (a label which indicates if the value represents a index, ar atribute or a class) and the value itself. After that, the data structure could be a list of lists, where each row is a list, and the dataset itself is formed as a list of rows (which are lists). However, if the dataset is big enough, I think this approach would be really really slow, but I have not been able to find a better data structure.

Any kind of help or resource for further research is welcomed.

$\endgroup$
  • $\begingroup$ Also posted on CSTheory.SE. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. If you don't get a satisfying answer after a week or so, feel free to flag for migration. $\endgroup$ – D.W. Feb 5 '16 at 4:24
  • 2
    $\begingroup$ I find it hard to tell what you are asking. 1. Why do you insist on describing your data structure with mathematics? Normally the way we describe a data structure is, well, by describing it: listing the operations that it should support, and what each does. 2. You don't describe/specify what your data structure should be able to do, so I'm not sure how to translate that into mathematics: it seems like the first step is for you to articulate a clear specification of what operations you want your data structure to support. $\endgroup$ – D.W. Feb 5 '16 at 4:44
  • 1
    $\begingroup$ 3. "Here's my idea; please give me feedback on it" tends not to be an ideal fit for this site's format, as it is so open-ended. We prefer answerable, technical questions that admit a correct answer. 4. Please define all terms before using them (e.g., "indexes", "classes"). It's confusing that you say that you have $q$ columns but later you say each row has (such-and-such structure); normally saying that the matrix has $q$ columns would mean that each row has $q$ cells. It's not clear what is the relationship among $q,n,m,k$, or what is the meaning of the indexes, attributes, and classes. $\endgroup$ – D.W. Feb 5 '16 at 4:47
  • $\begingroup$ This is for work. The boss does want it to be done with equations (don't know why). q and p have no relationship and you can tell that each row have q columns, so that q = m + n + k. The meaning of indexes, attributes, classes it's as follows: indexes are values that help identify a row (the combination of the n indexes must be unique for each row). The attributes are values that are proper to a certain row, and will be used to do some processing. Based on that, a result value would be obtained, and using that value the specific row would be fit into one of the classes. All values are string. $\endgroup$ – addictedtohaskell Feb 6 '16 at 6:02
  • $\begingroup$ No one knows until now, which operations will be needed by the structure, but what I can tell so far, is that its goal is to allow some regression and classification methods to be run over it. So, for now, I think the most important characteristics would be 1) allow fast insert of the data. 2) Allow fast retrieval of the data 3) Optional: allow fast search of the data. $\endgroup$ – addictedtohaskell Feb 6 '16 at 6:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.