# Efficient Interval Queries

**URL:** <https://discuss.elastic.co/t/efficient-interval-queries/10335>\
**Category:** Elasticsearch\
**Created:** [January 14, 2013, 6:47pm UTC](https://discuss.elastic.co/t/efficient-interval-queries/10335 "2013-01-14T18:47:55Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![btiernay](https://avatars.discourse-cdn.com/v4/letter/b/bb73d2/32.png) [@btiernay](https://discuss.elastic.co/u/btiernay)\
**Post date:** [January 14, 2013, 6:47pm UTC](https://discuss.elastic.co/t/efficient-interval-queries/10335/1 "2013-01-14T18:47:55Z")

</div>

A common use case for certain types of data is the ability to search for  
documents that have an interval field that overlaps or that is contained in  
a target interval. Typically, this is implemented using an Interval Tree[http://en.wikipedia.org/wiki/Interval\_tree](http://en.wikipedia.org/wiki/Interval_tree) or  
a Range Tree [http://en.wikipedia.org/wiki/Range\_tree](http://en.wikipedia.org/wiki/Range_tree) in other contexts.

I was wondering if ElasticSearch (or Lucene) provided such a capability,  
perhaps by leveraging n-grams or geo-spatial indexes.

Thanks!

--

---

<div class="post-metadata">

**Author:** ![jprante](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/jprante/32/44941_2.png) [@jprante](https://discuss.elastic.co/u/jprante)\
**Post date:** [January 14, 2013, 11:37pm UTC](https://discuss.elastic.co/t/efficient-interval-queries/10335/2 "2013-01-14T23:37:49Z")

</div>

Lucene uses tries in range queries since  
Schindler/Diepenbroek, [http://epic.awi.de/17813/1/Sch2007br.pdf](http://epic.awi.de/17813/1/Sch2007br.pdf)

Best regards,

Jörg

--

---

<div class="post-metadata">

**Author:** ![btiernay](https://avatars.discourse-cdn.com/v4/letter/b/bb73d2/32.png) [@btiernay](https://discuss.elastic.co/u/btiernay)\
**Post date:** [January 15, 2013, 2:20pm UTC](https://discuss.elastic.co/t/efficient-interval-queries/10335/3 "2013-01-15T14:20:23Z")

</div>

Hi Jörg,

Thanks for this very informative reference. I was very curious how Lucene  
was performing RangeQueries, and this certainly gives a better explanation  
than the Javadocs. So, if I understand the approach correctly, one should  
be able to use a document structure with two fields, say start and end.  
Both of these fields should be NumericField. Then, two RangeQueries can be  
specified to efficiently (by way of the two prefix tries) find all  
documents that are contained in a target interval. Is my understanding  
correct?

Cheers

On Monday, 14 January 2013 18:37:49 UTC-5, Jörg Prante wrote:

> Lucene uses tries in range queries since Schindler/Diepenbroek,  
> [http://epic.awi.de/17813/1/Sch2007br.pdf](http://epic.awi.de/17813/1/Sch2007br.pdf)
> 
> Best regards,
> 
> Jörg

--

---

<div class="post-metadata">

**Author:** ![system](https://us1.discourse-cdn.com/elastic/original/3X/1/a/1ac57faf039f6b580b3f104ef42a2a89e41014de.png) [@system](https://discuss.elastic.co/u/system)\
**Post date:** [July 6, 2017, 2:56am UTC](https://discuss.elastic.co/t/efficient-interval-queries/10335/4 "2017-07-06T02:56:22Z")

</div>