Questions regarding efficient storing and representing data within a software application.

learn more… | top users | synonyms

6
votes
2answers
1k views

Is a tree with nodes that have reference to parent still a tree?

If we make reference to the parent for each node in a tree, do we still have a tree (by definition) anymore? Wikipedia definition is: In computer science, a tree is a widely used abstract data ...
6
votes
6answers
265 views

Should I always store parsed data in database before manipulating?

I am about to start a new project which involves taking an excel file, parsing the data (php-excel-reader) and then using the parsed values in a HTML email. My question is pretty simple. Is it better ...
6
votes
1answer
2k views

Where to learn graph theory applications [closed]

I am completely new to designing algorithms with graphs. I am following CLRS and other video lectures in Youtube, notably from IIT/MIT. They are pretty good, and I currently have decent idea about ...
6
votes
4answers
866 views

Representing a rule in a ruleset

How to represent rules for a rule engine as objects? A rule would be if (booleanExpression(input)) then a chain of generic actions" else next rule ...where the generic actions might be e.g. ...
6
votes
4answers
617 views

Is there a way to track data structure dependencies from the database, through the tiers, all the way out to a web page?

When we design applications, we generally end up with the same tiered sets of data structures: A persistent data structure that is described using DDL and implemented as RDBMS tables and columns. A ...
6
votes
4answers
610 views

Understanding the Macro Aspects of Data Structures

I am studying data structures right now, but I still need to find a teacher/site/book with a clear explanation of the macro aspects of this topic. What I mean is: most lessons/text books mix ...
6
votes
3answers
2k views

How do you choose a programming/data structure/algorithm book? [closed]

I really should not be mentioning the name of the book, but the first time I read it (during my under-grad days) I almost concluded that data structure was a bad course to pick. Which brings me to ...
6
votes
3answers
1k views

Faster reads, on an infinite grid plane, than using a hash table?

In the past, I've had alot of success just using a .NET Dictionary, with a TKey consisting of the X,Y coordinates merged together. However its read performance, despite being amortized constant time, ...
6
votes
2answers
4k views

Nested Enum type in C++ or C#?

I've come across a recurring issue in a few of my recent projects in which I find myself using enums to represent state, or type, or something else, and I need to check against a few conditions. Some ...
6
votes
1answer
3k views

What is the usage of Splay Trees in the real world?

I decided to learn about balanced search trees, so I picked 2-3-4 and splay trees. What are the examples of splay trees usage in the real world? In this Cornell: ...
6
votes
2answers
2k views

What data structure could I use for modeling a network of nodes and edges?

My application needs to model of and perform operations on a network with 40 - 50 nodes and typically less than 6 edges per node. Both nodes and edges are objects with around 1K data each. During ...
6
votes
3answers
450 views

Hashing growth strategy

What is a good growth strategy for hash tables? If the number of elements exceeds the number of buckets, I increase the number of buckets with the following formula: n = int(n * 1.618033988749895) | ...
6
votes
1answer
581 views

Algorithm/data structure to answer “what recipes can I make with this set of ingredients?”

Formally, let s(U, Q) = {V | V ∈ U and V ⊆ Q} where U, Q, and V all represent sets, and U, more specifically, represents a set of sets. For the sake of example, U might be a set of the (sets of) ...
6
votes
1answer
176 views

Unit testing a text index

Consider a text index such as a suffix tree or a suffix array supporting Count queries (number of occurrences of a pattern) and Locate queries (the positions of all the occurrences of a pattern) over ...
6
votes
4answers
1k views

Writing a new programming language - when and how to bootstrap datastructures?

I'm in the process of writing my own programming language which, thus far, has been going great in terms of what I set out to accomplish. However, now, I'd like to bootstrap some pre-existing data ...
6
votes
1answer
320 views

How to design data structures for sharding?

When designing data structures for an application, what are some best practices to make sure it can be sharded? In particular, which of the following is better: Creating relationships in databases ...
6
votes
1answer
562 views

Min cost concatenation alignment [closed]

I am doing a project on data mining. I have a very large string of size, say n and many small strings, l_1,l_2.. each of size at most m. I want to find the sequence of small strings such that their ...
5
votes
2answers
1k views

Overriding GetHashCode in a mutable struct - What NOT to do?

I am using the XNA Framework to make a learning project. It has a Point struct which exposes an X and Y value; for the purpose of optimization, it breaks the rules for proper struct design, since its ...
5
votes
1answer
399 views

Can anyone explain to me what problem Core Data solves? [closed]

Core Data seems to add a needless layer of complexity. If you want to save data created natively by the user in an app why not just use an object and then write the data all to SQLite or back to a ...
5
votes
2answers
910 views

Do you get the benefits of a B-Tree in a managed language?

My understanding is that one of the key features of a B-Tree (and a B+Tree) is that it is designed such that the size of its nodes are some multiple of the block size of whatever media the data is ...
5
votes
6answers
1k views

What's the difference between a stream and a queue?

What's the difference between a stream and a queue? They both have the concept of an ordered set of elements, but tend to have different implementations and a different vocabulary of ...
5
votes
3answers
145 views

How to create “constructors” for structures in C

The problem I have this structure that I want to create a "constructor" for it. struct example { int x, y, z; /* various members */ struct another *another; /* pointer to another structure ...
5
votes
2answers
369 views

Why Do B+ Trees Have a Minimum Occupancy of 50%?

As far as I can tell, the basic operations (add, delete, search) on a B+ Tree would function the same if minimum occupancy was 1, or 1/3, or any other function on node size. All the sources available ...
5
votes
2answers
580 views

Is it safe in Haskell to save a data structure to a file using “show”, and retrieve it using “read”?

Say I have the following types: type EndsTup = (Int,Int) -- (0-based index from start or end, Frequency) type FreqTup = (Char, [EndsTup], [EndsTup]) -- (Character, Freqs from start, Freqs ...
5
votes
1answer
152 views

Is it possible to have these characteristics in a data structure?

I was tutoring a student that came up with this assignment. It basically requires a data structure with the following characteristics: it holds a set of integers in {1, 2, ..., n} n is power of 2 ...
5
votes
2answers
1k views

Is it possible to speed up a hash table by using binary search trees for separate chaining?

I want to implement a Hash Table using Binary Search Trees to reduce the search complexity in the Separate Chaining process from O(n) (using linked list) to O(log n) (using BST). Can this be done, and ...
5
votes
2answers
6k views

Optimal way to store 18 billion key, value pairs [closed]

I have around 200 million new objects coming in, and a 90 day retention policy, so that leaves me with 18 billion records to be stored in the form of key-value pairs. Key and value both will be a ...
5
votes
2answers
435 views

How can a true Vector be implemented in Haskell?

How could a true Vector type be implemented in Haskell? In order for something to be a Vector, it has to be stored sequentially in memory, with O(1) random access. But Haskell hides its memory ...
5
votes
7answers
2k views

Priority list of tasks stored in a database

I am trying to think of the best way to do the following: I have a list of tasks stored in the database. A task has a priority assigned to it. You can change the priority of a task to reorder the ...
5
votes
4answers
479 views

Quadtree with duplicates

I'm implementing a quadtree. For those who don't know this data strucutre, I am including the following small description: A Quadtree is a data structure and is in the Euclidean plane what an ...
5
votes
2answers
2k views

Creating huge decision tree

I'm to write an event correlator. A fundamental part of the system will be a decision tree that recognizes the origin of the fault basing on recorded states and log files. Often many accidents will ...
5
votes
2answers
2k views

Data structure for pattern matching

Let's say you have an input file with many entries like these: date, ticker, open, high, low, close, <and some other values> And you want to execute a pattern matching routine on the ...
5
votes
4answers
276 views

Is there a pattern that will help with this data structure

I'm doing a java project. My main structure contains 2 lists with elements of type A the other type B. B itself contains a list of objects which may contain elements of A. It must be that when an ...
5
votes
1answer
478 views

How to store satellite data in C data structures

I've been reading through Introduction To Algorithms 3rd Ed, and I am having difficulty in implementing some practical situations. It's not the theory, or implementing the internals of the data ...
5
votes
1answer
4k views

Homogeneous vs. heterogeneous AST representation

What are the reasons to choose a homogeneous vs. a heterogeneous AST representation for implementing a complex domain-specific programming language? Just to be very clear about what I'm asking, here ...
5
votes
2answers
611 views

Fast set indexing data structure for superset retrieval

I am given a set of sets: {{a,b}, {a,b,c}, {a,c}, {a,c,f}} I would like to have a data structure to index those sets such that the following "lookup" is executed fast: find all supersets of a given ...
5
votes
1answer
210 views

Bloom filters or similar, but with no false positive

To improve some lookups, I am considering the use of Bloom Filters. But in my use-case, the most probable outcome is that the element do exists in the target set. Bloom filters can have false ...
5
votes
2answers
359 views

Data structures for storing finger/stylus movements in drawing application?

I have a general question about creating a drawing application, the language could be C++ or ObjectiveC with OpenGL. I would like to hear what are the best methods and practices for storing strokes ...
5
votes
3answers
170 views

Maintaining a list of nodes with challenging requirements

This is a question regarding the design of a collection of ordered nodes which have some requirements that I am struggling to satisfy. In the problem area that I am dealing with we have routes which ...
5
votes
1answer
93 views

How does cuckoo hashing guarantee O(1) lookups in presence of persistent hash collisions

Most hash table implementations guarantee O(1) average case but O(n) maximum case for lookup (where 'n' is the number of keys in the table). But Cuckoo Hashing is described as O(1) maximum. ...
5
votes
2answers
1k views

Efficient Data Structure for holding a graph

Problem Link - http://opc.iarcs.org.in/index.php/problems/NUMTRIPLE In my opinion, the problem can be solved by a data structure, that shows how each number is connected to another, and via recursion ...
5
votes
1answer
360 views

Efficient data structure to implement fake file system

I want to implement a data structure that will hold the paths of directories, sort of fake file system. Input:- I have a text configuration file containing the paths as follows ... C:/temp1 ...
5
votes
1answer
3k views

Building a Graph Editor - How to create a data driven graph

I am developing a graph-editor that uses drag and drop to build hierarchical graphs (containing nodes and links). Each node in the graph should be linked to a table in our database (SQL Server). I did ...
5
votes
3answers
406 views

Generating Deep Arrays: Shallow to Deep, Deep to Shallow or Bad idea?

I'm working on an array structure that will be used as the data source for a report template in a web app. The data comes from relatively complex SQL queries that return one or many rows as one ...
5
votes
4answers
298 views

Users creating instances from a template - is there a software pattern that corresponds to this use case?

I am looking into designing a system where users build a template item and then create many instances based on this template.They then need to be able customise each instance but I also need for them ...
4
votes
4answers
9k views

Is it wise to store a big lump of json on a database row

I have this project which stores product details from amazon into the database. Just to give you an idea on how big it is: [{"title":"Genetic Engineering (Opposing ...
4
votes
5answers
831 views

Is my understanding of abstract datatypes correct?

After reading lots of pages on various sites, I came to the conclusion that abstract datatype helps to separate the use of datastructure from its implementation. We can easily map the data into a ...
4
votes
10answers
1k views

Standardized Data Structure Interface

I want to work with a variety of data structures (arrays, singly/doubly linked lists, sorted structures, etc.) on a plug-and-play basis. For example, I want to be able to easily swap in and out the ...
4
votes
5answers
2k views

How do you cope with Java coming from javascript?

I learned some javascript as my introduction into programming, and now I'm trying to move on to Java and Python and from there to c++, c#, etc. I've been caught up with schoolwork, so I've had very ...
4
votes
2answers
491 views

Is there any particular reason for the use of lists over queues in functional programming languages?

Most functional programming languages such as Scheme and Haskell use lists as their main data structure. Queues are identical to lists, except for the fact appending to the end - not to the begin - ...