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

learn more… | top users | synonyms

5
votes
2answers
268 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
382 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
2answers
3k views

Amortized Analysis? (Worst-case Performance Guarantees)

What is Amortized Analysis? And how can it help me achieve worst-case performance guarantees in my programs? I was reading that the following techniques can help the programmer achieve Worst-case ...
5
votes
1answer
997 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 ...
5
votes
3answers
847 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 ...
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
2answers
4k 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
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
1answer
132 views

Is there a design pattern for managing deep many-to-many relationships?

I'm having trouble defining this data pattern I've come across working on several applications. It consists of: An object type which is composed of many objects itself A second object type, where ...
5
votes
1answer
385 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
2answers
1k 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
2answers
314 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
165 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
154 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
927 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
2k 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
384 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
276 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
5answers
531 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
2answers
430 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 - ...
4
votes
2answers
3k views

Is there a way to handle nested Collections more elegantly?

My question is rather a design question. In my program I got to a data structure that looks something like this: private ConcurrentHashMap<A, ConcurrentHashMap<B, ConcurrentHashMap<Integer, ...
4
votes
2answers
4k views

What is the advantage of using map datastructure?

I am a member of some online coding website and today when I submitted a solution in C++, I saw there were much better answers in C++ itself which took considerably less time. The solutions were open ...
4
votes
2answers
392 views

Are bloom filters actually faster than hashes, even taking in account cache?

Bloom filters look really great when you consider you can determine if an Int is in a set with 99% certainty in constant time. But so can hashes, with the only difference that, in a hash, most of the ...
4
votes
4answers
302 views

Why use an enum to determine node type in a parse tree?

The Sun Compiler Tree API uses an interface called Tree as the parent of all the different kinds of parse tree nodes (assignments, if-statements, class declarations, etc.). A part of this interface is ...
4
votes
3answers
7k views

How can I practice implementing data structures and algorithms? [duplicate]

I just finished learning the basics on data structures and algorithms using Python and C, completing some of the exercises from the book I read. I feel that it is necessary to implement some of these ...
4
votes
3answers
3k views

Data Oriented Design - impractical with more than 1-2 structure “members”?

The usual example of Data Oriented Design is with the Ball structure: struct Ball { float Radius; float XYZ[3]; }; and then they make some algorithm that iterates a std::vector<Ball> ...
4
votes
2answers
316 views

Is this data model a list or tree?

Using python syntax with below environment diagram, teacher taught us that there are 11 trees(orange boundary) in this diagram, including leaf. It has been taught here, lists are represented as a ...
4
votes
4answers
446 views

Building a route creator

Ok, already up front, I'm going to tell you, that this is a bonus task for Data structure course I'm taking. That should take care of all the questions whether or not this is for a homework. Route ...
4
votes
4answers
730 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 ...
4
votes
2answers
1k views

Which design better when use foreign key instead of a string to store a list of id

I'm building online examination system. I have designed to table, Question and GeneralExam. The table GeneralExam contains info about the exam like name, description, duration,... Now I would like to ...
4
votes
2answers
508 views

Data Structures: What are some common examples of problems where “buffers” come into action?

I was just wondering if there were some "standard" examples that everyone uses as a basis for explaining the nature of a problem that requires the use of a buffer. What are some well-known problems in ...
4
votes
3answers
1k views

Is it conceivable to have millions of lists of data in memory in Python?

I have over the last 30 days been developing a Python application that utilizes a MySQL database of information (specifically about Norwegian addresses) to perform address validation and correction. ...
4
votes
4answers
245 views

Useful Pre-requisites for Operating Systems course?

How important is knowledge of data structures and algorithms for an Operating Systems and Systems Programming course where we will be required to design and implement a kernel of a real-time operating ...
4
votes
1answer
232 views

Why define struct in variable?

Consider the following program: Many people when they want to use a struct, they create a new variable as: struct structureName variableName While it works when you just define it as: ...
4
votes
2answers
207 views

Decimal vs. Integer; Given a fixed range of values, which is preferable for accurate computation?

After getting into a "heated discussion" with someone, I figured I'd ask this question for the sake of posterity. I'm willing to be corrected if my assumption is incorrect but I'd like to hear a ...
4
votes
2answers
271 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 ...
4
votes
3answers
719 views

How Immutable Sets are Manipulated

When working with an immutable set or map, like the ones found in many functional programming languages, operations that would otherwise modify the container generate a new container instead. I know ...
4
votes
4answers
628 views

Appropriate data structure for deeply nested data?

I can't figure out what would be an appropriate data structure for my problem. I need to write a script that will count some events. Input is a list of events (thousands of them). Each event is an ...
4
votes
2answers
89 views

Mutable AST vs. different immutable ASTs

I am writing a toy compiler. During the semantic passes, I want to add information to the AST. Which of the following is the best approach? Define 1 mutable AST type whose fields are updated with ...
4
votes
1answer
3k 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 ...
4
votes
2answers
532 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 ...
4
votes
3answers
226 views

Picking powers of two for sizes/limits

A habit I've observed among programmers, and a habit I sometimes subconsciously exhibit myself, is to pick powers of two (or powers of two minus one) when defining a database schema, a data buffer, ...
4
votes
4answers
286 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 ...
4
votes
2answers
1k views

Patterns for a tree of persistent data with multiple storage options?

I have a real-world problem which I'll try to abstract into an illustrative example. So imagine I have data objects in a tree, where parent objects can access children, and children can access ...
4
votes
1answer
524 views

Amazon Kindle - Whispersync implementation?

For those who are not aware of Kindle's whispersync, here is how it works (from amazon.com): "...Whispersync synchronizes the bookmarks and furthest page read among devices registered to the same ...
4
votes
1answer
343 views

Website with test data files for specific algorithms/data structures?

Is there any website, like SPOJ and Project Euler, with the test data files available for specific algorithms/data structures? I know it's a fun challenge to solve those problems on your own, but I ...
4
votes
1answer
54 views

What method should I use to populate a tree as I'm consuming data that is contained within the tree?

I have a tree that consists of 5 types of nodes - V, W, X, Y, and Z. V represents the root node, and a given tree has exactly one element of type V. A V contains one or more Ws, a W contains one or ...
4
votes
1answer
159 views

How to store data that is recorded with different frequency?

I'm writing a metallurgical web application, that must store data (electrical parameters) recorded at different frequencies. For example: six parameters recorded with frequency of one measure per ...
4
votes
2answers
150 views

Incremental and partial drawing of the large graphs

I have the following problem: I'm developing a software for data visualization where I get a graph structure and represent it in 3D space. So far, I've been using force-based algorithms to draw graphs ...
4
votes
2answers
102 views

Is it a good idea to have a database row that represents an unknown value within a system [closed]

We have two systems, System A imports a list of sports events from system B, it only wants to import the events we will be providing live data for, the filter used to hide events that we are not ...