Skip to content

Automatically exported from code.google.com/p/segment-trees

Notifications You must be signed in to change notification settings

mikemccand/segment-trees

Folders and files

NameName
Last commit message
Last commit date

Latest commit

710f07b · Dec 12, 2013

History

13 Commits
Dec 9, 2013
Dec 12, 2013
Dec 9, 2013
Dec 12, 2013
Dec 9, 2013

Repository files navigation

This project contains fast Java implementations of <a href="http://en.wikipedia.org/wiki/Segment_tree">segment trees</a>, which are binary tree structures to efficiently locate all ranges overlapping a given point.

See <a href="http://blog.mikemccandless.com/2013/12/fast-range-faceting-using-segment-trees.html">this blog post</a> for details.

Segment trees require O(log(N) + M) time for each query ("find all ranges overlapping a point"), where N is the total number of ranges and M is the number of ranges matching the current point.  After the crossover point (~10 ranges or so), segment trees are faster than a simple linear search.

The code is exploratory; there are various implementations, some slow, some fast.

Currently, only long values are supported, and there are different implementations of LongRangeMultiSet to look up all ranges overlapping a given values, as well LongRangeCounter to count the number of times each range occurs across a number of values.  Ranges are allowed to overlap, so multiple ranges can match a given point.

Under the hood I use the <a href="http://asm.ow2.org/">ASM</a> library to create specialized Java bytecode (pass useAsm=true to Builder.getCounter and Builder.getMultiSet) to find matching ranges for a given point and increment counts; this simplifies the implementation (no more recursion, for loops, etc.) and makes it quite a bit faster in certain cases (up to 2.5X in the micro-benchmarks, PerfTestMultiSet and PerfTestCounter).

About

Automatically exported from code.google.com/p/segment-trees

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages