Scalable Range Search over Temporal and Numerical Expressions

Venue: ACM_org_SIGIR_ICTIR_2024_Conference
Published: 2024-04-24 14:09:22

Abstract: Natural language expressions of time and numbers can be ambiguous (e.g., "2020s" can refer to either 2021 or 2025), can be present at different granularities, or can be unbounded (e.g., "more than ten percent"). To match and retrieve such ambiguous temporal and numerical expressions over millions of documents, we present NASH. Our experiments on collections amounting to more than 22 million documents show that NASH provides significant speedups in the order of 19.23 - 53.10x for contains and near queries. NASH manages this while using indexes that are 1.90 - 2.05x smaller than the indexes utilized by baselines. We further demonstrate NASH's scalability to the Web by indexing a subset of Common Crawl amounting to more than 365 million documents.

Main paper: 
 introduction: 
 The Web is a knowledge-rich repository of real-world events as they have unfolded over time. Event analytic tasks require retrieval of documents containing combinations of words, entities, temporal and numerical expressions. Important events are marked by the days, months, or years (e.g., recession in '24 ) which they spanned and are often characterized quantitatively by numbers (e.g., 10% inflation ). To retrieve documents that contain time intervals and numerical values that are of relevance to the ones mentioned in the query is challenging. The first challenge is of performing a semantic match between the queried interval and the intervals described by the temporal and numerical expressions in text (e.g., matching the ambiguous expression around ten percent to the query term 11%). The second challenge is that of the design of a data model such that we can store the values of the temporal and numerical expressions with their precise semantics so as to accommodate their hierarchical (e.g., day ≺ month ≺ year) and proximate relationships. The third and final challenge we face is that of performing the semantic match at scale across Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. ICTIR ' Inflation is more than ten percent this year in the US. The annotated text model [18, 19] .millions of documents. Specifically, the number of implicit intervals referred by 2000s or around 10% can be arbitrarily large, how can we match the time interval expressed in the query to these numerous variations during query processing and avoid inspecting irrelevant intervals (e.g., by naïvely scanning an interval index over the begin and end of the temporal and numerical expressions)? nash enables querying for temporal and numerical intervals using range-based operators (i.e., contains, containedBy, intersect, and near). To do so, nash models ambiguous temporal or numerical expression using two-dimensional geometry to overcome the challenge of semantic gap. To store these two-dimensional geometries associated with temporal and numerical expressions, nash utilizes z-order curves [26] . By utilizing z-order curves, we can query temporal and numerical intervals at different levels of granularity by simply truncating bits of the hash values. Finally, we describe the concept of continuous hashes and an improved variant of bigmin and litmax method [34] to optimize query processing for nash. 
nash: 
 We now describe our system nash in detail.Annotated Text Model. We build upon the text model [18, 19] , where each document 𝑑 in a collection 𝐷 is modeled as a collection of annotation layers: 𝑑 L = ⟨ℓ [𝑖,𝑗 ] . . . ℓ [𝑝,𝑞 ] ⟩. The annotations ℓ are drawn from the annotator's (e.g., a named entity tagger) vocabulary Σ L (e.g., person, organization, location, date, number). Furthermore, each annotation ℓ [𝑖,𝑗 ] adorns a contiguous word sequence ⟨𝑤 [𝑖,𝑖 ] , . . . , 𝑤 [ 𝑗,𝑗 ] ⟩ in the word layer 𝑑 W (see Figure 1 ).Temporal and Numerical Expressions in text can be obtained by annotators such as Stanford CoreNLP [25] . Specifically, coarsegrained named entity annotations indicated by time, date, money, number, percent, ordinal can be resolved to precise intervals with the help of rule-based taggers, such as SUTime [13] . Thus, we can resolve implicit, relative, and explicit mentions of time and numbers to exact intervals based on document metadata or explicit dates or numbers mentioned elsewhere in the document contents. Note that unlike temporal expressions, resolved values for numerical expressions can be unbounded (e.g., > 10%) or approximate (e.g., ∼ 5 ).Uncertainty-Aware Model. Temporal and numerical expressions in text (e.g., around millions) often convey an interval [𝑏, 𝑒] which is ambiguous. The uncertainty-aware model [11] represents this ambiguity by allowing for lower and upper bounds to the beginning and the end of intervals. Thus, we can model uncertainty as a quadruple: ⟨𝑏 𝑙 , 𝑏 𝑢 , 𝑒 𝑙 , 𝑒 𝑢 ⟩, where, the lower 𝑙 and upper 𝑢 bounds allow ambiguity in the beginning 𝑏 and end 𝑒 of the interval (𝑏 ≤ 𝑒). Thus, a temporal or numerical interval (e.g., early '20s) can be represented as a two-dimensional bounding box in a Cartesian plane as shown in Figure 3a and refer to its intervals (e.g., [1922, 1925] ) as a region in the Cartesian plane.Space-Filling Curves provide a way of linearizing multidimensional values by traversing every point of a 𝑛-dimensional region and mapping the multidimensional data to a position on an onedimensional curve. Thus, any 𝑛-dimensional point can be described by its unique 1-dimensional position on a linear curve. In this work, our focus will be on space-filling curves and their applications in two-dimensional space.The Quadtree [17] is a common technique used for spatial indexing. Quadtrees share some characteristics with space-filling curves, such as: the space division into regions and visualization of the hierarchical characteristics as a tree. The quadtree is a generalization of the binary tree for treating data in two dimensions. A binary tree recursively splits a one-dimensional space in two, resulting in a maximum of 2 𝑛 nodes at each level, starting with 𝑛 = 0 at the top level. The quadtree functions similarly but in two dimensions. Each dimension is split in two, resulting in four total children and thus 4 𝑛 nodes of each level. The region quadtree is a variant of the quadtree where the space is divided into equal size regions. Each region then represents a two-dimensional range, i.e., a minimum bounding rectangle. All points in the two dimensional space will then belong to one of these regions. Figures 2a and 2b show how a two-dimensional space can be broken into smaller quadrants with the corresponding tree-representation. The treerepresentation also illustrates the hierarchical characteristic of the quadtree. The parent-child relationship of nodes means that all child nodes of the same parent node are all contained by the parent region.To retrieve documents for event-centric queries, we next explain the range-based operators that are part of nash's query language.Range-Based Operators. nash provides three important rangebased operators: contains and containedBy; intersect; and near. We next define the semantics of each of the operators formally. The contains operator allows for retrieval of those documents that have an interval which lies completely within the queried interval. Another variation of the operator is containedBy which retrieves those documents having intervals which completely subsume the queried interval. The semantics of contains (semantics of con-tainedBy can be derived similarly) for a queried temporal or a numerical interval [𝑏, 𝑒] can be defined as:EQUATIONThe intersect operator as the name suggests would retrieve those documents that contain a temporal or numerical annotation whose interval representation intersects with the queried interval. The semantics of intersect operator can be formalized as:EQUATIONThe final operator near retrieves those documents that contain a temporal or numerical annotation whose interval representation is in proximity to the query interval. The proximity function (e.g., Euclidean distance) is defined during indexing of the document collection and allows us to retrieve those documents quickly within a given margin Δ. The semantics of the near operator is defined as:near(ℓ) = 𝑑 ∈ 𝐷 | (ℓ ′ ∈ 𝑑 L ) ∧ (distance(ℓ, ℓ ′ ) ≤ Δ) . (3)A naïve approach to searching temporal and numerical intervals would be to index each dimension of the interval (e.g., begin and end) and evaluate the range-based search predicates. However, either with a naïve interval representation or the uncertainty-aware interval representation this would require multiple scans over the indexes to determine the result set. An alternative approach can be to utilize known indexing techniques for multidimensional data [33] . However, these approaches are more involved and hard to accommodate in the query processing engine of a large scale search infrastructure that primarily relies on inverted indexes. To bring together a unified indexing solution to annotated text documents we turn to space-filling curves, which allow us to map multidimensional data into one-dimensional summaries that can then be queried using inverted indexes. Space-filling curves also exhibit localitypreservation property such that geometries or data points in high dimensional spaces that are close together are allocated proximate hash values. This provides data locality on disk thereby aiding in quick query processing. Furthermore, space-filling curves inherently provide hierarchical relationship between coarser-granular regions and finer-granular regions (similar to QuadTrees for indexing spatial data [17] ). This property of space-filling curve is particularly important as it also allows us to capture the hierarchical relationship in temporal expressions mentioned at different granularities (i.e., day ≺ month ≺ year). For our purposes, as temporal and numerical intervals are represented in the uncertainty-aware representation, we are concerned with mapping two-dimensional bounding boxes to one-dimensional summaries.z-order Curves. We utilize z-order curves [26] for computing the hash values. Other space-filling curves such as Hilbert curves [21] allow for higher precision and better locality preservation but at an increased computation cost. A z-order curve partitions the Cartesian space recursively into four disjoint regions. To assign a unique value to each of these regions the curve traverses through each of them exactly once in a "z" manner. The z-order hash for a region can be arrived by interleaving the bits representing the coordinate positions spanning the partitions (see Figure 3b ).Using the z-order curve, we can now model the uncertaintyaware representation of temporal and numerical expressions. This is done by breaking down the bounding-box corresponding to the expression and computing z-order hashes for the resulting regions.The accuracy of the z-order hash representation of the boundingbox is given by the size of the smallest possible region. The size of a region can be computed by the number of bits and the size of the dimensions being represented. For a range [𝑏, 𝑒] and 𝑛 bits to describe one dimension, accuracy can be defined as:EQUATIONz-order Hash Computation is shown in Algorithm 1. The cal-culateHash method takes as its input the co-ordinates for which the z-order hash needs to be computed, the overall range for temporal or numerical expression in the entire document collection, and the required precision of the hash. The overall range is defined by an interval, where the begin is the earliest time point or the smallest numerical value while the end is the latest time point or the largest numerical value to occur in the entire document collection. The z-order value is calculated one bit at a time, starting with the most significant bit (MSB). This represents the first Y-value of the hash. A counter 𝑏 is used to indicate the current bit position. If the position is even, the current bit represents a part of the 𝑌 -value, and if not, it represents a part of the 𝑋 -value. The calculation of the current bit is the same for both dimensions. The mid-point of the current dimension is calculated and compared against the mid-point of the current range for that dimension. It starts as the 𝑋 and 𝑌 dimension bounds and is halved for each bit being calculated. If the value is larger than or equal to the midpoint, the current bit position is set to 1, and if not, it stays at zero. The range of the current dimension is then halved, keeping the half containing the value. This is done alternately for the 𝑋 and 𝑌 dimension, until the desired number of bits or precision is reached.Decoding of the z-order hash is done in a similar manner. Starting with the MSB, if the bit is a 1, the overall range of the dimension (starting with Y) is split into the upper half, and if the bit is 0 into the lower half. This is done for each bit, each time halving the range for the current dimension being examined. The result is then an interval for each dimension, indicating the region the z-order hash covers.As the range search over the z-order curve is done at a minimum of two bits at a time, a base 4 encoding is used. That is, each base 4 character represents one partition in both the X and the Y dimension. This results in a shorter representation while still allowing for the finest precision increment or reduction by adding or removing from the hash. Moreover, it allows for any even level of z-order precision while indexing and querying. The encoding is as simple as translating each 𝑋 , 𝑌 pair into its base 10 representation: 00 2 → 0 10 , 01 2 → 1 10 , 10 2 → 2 10 , 11 2 → 3 10 .z-order Hash Indexes. To leverage the benefits of the spacefilling curves outlined earlier, we instantiate an inverted index that stores the z-order hash along with their positions. The positional information can further help us to compute the shorter text regions within documents that can contain them in sequence with other annotations (e.g., named entities). With this index design choice, we leverage the locality-preservation property of the z-order curves. This is because the points close in the uncertainty-aware model are also stored close together in the index (since the indexes are sorted by the indexing units). Furthermore, we additionally index the prefixes of each of the z-order hashes to leverage the hierarchical property of the space-filling curves. For example, for the hash 3300030030 corresponding to the range [1890, 1890], each prefix 330003003, 33000300, 3300030, etc. are indexed at the same positional span. Therefore, by truncating bits from a hash we can move from fine granular representation of the interval (e.g., at day-level) to a coarse-granular representation of the interval (e.g., at yearlevel). Concretely, z-order hash indexes store for each occurrence of the hash and its prefixes, the following particulars in the document collection: the document identifiers, the sentence identifiers, the begin positions in the document, and the end positions in the document (see Figure 4 ). The sentence identifiers and positional information allows us to further compute concise text regions containing temporal and numerical expressions in combination with other word sequences and coarse-grained named entities (e.g., person, organization, or location). The payloads for each of the hashes are further compressed using patched frame of reference [6, 38] . Index Combinations are often leveraged for Web-scale query processing [18, 28, 36] . To evaluate event-oriented queries, we additionally require indexes over n-grams (unigrams, bigrams, and trigrams) and coarse-grained named entities (e.g., person, org., and loc.). To construct these indexes, we rely on the same index structure as that of the z-order hash indexes.Using the z-order hash-based indexes we can now convert search over the uncertainty-aware model into a simple linear range search over the hashes. This naïve approach entails, creating the query-MBR (minimum bounding rectangle) that describes the interval to be searched having been represented in the uncertainty-aware model. The resulting matches can then be obtained by retrieving all the z-order hashes that lie between the diagonally opposite hashes describing the query-MBR. Due to the nature in which the z-order curve jumps across partitions, there are bound to be some false-positives. However, we are guaranteed to always retrieve all of the relevant temporal or numerical expressions with this naïve approach. We next describe the query-MBR generation for the four query predicates (see also Figure 3c ).Query MBRs for contains and containedBy. A contains query translates to the MBR described by 𝑋 ∈ [𝑏 𝑥 , 𝑒 𝑥 ] and 𝑌 ∈ [𝑏 𝑦 , 𝑒 𝑦 ] with 𝑋 ≤ 𝑌 . The result set can be obtained by retrieving all the hashes that lie between diagonally opposing corners of the MBR, i.e., (𝑏 𝑥 , 𝑏 𝑦 ) and (𝑒 𝑥 , 𝑒 𝑦 ). A containedBy query translates to the MBR described by 𝑋 ≤ 𝑏 and 𝑌 ≥ 𝑒, where the lower bound for 𝑋 and upper bound for 𝑌 is equal to the lower bound and upper bound for the overall range of temporal or numerical annotations being indexed for the document collection, respectively.Query MBRs for intersect. A intersect query translates to a MBR described by 𝑋, 𝑌 ∈ [𝑏, 𝑒] with 𝑋 ≤ 𝑒, 𝑌 ≥ 𝑏, where the lower bound for 𝑋 and upper bound for 𝑌 is equal to the lower bound and upper bound for the overall range of temporal or numerical annotations being indexed for the document collection, respectively. Thus, a intersect query includes results that would be obtained from a containedBy and contains query with additional results that intersect the queried interval.Query MBRs for near. We use the Euclidean distance as a measure of proximity to process a near query. A near query translates to a MBR described by the points [𝑏 -Δ, 𝑒 -Δ] and [𝑏 + Δ, 𝑒 + Δ] as being the diagonally opposing points. In that MBR, Δ denotes the distance within which an interval represented by a temporal or a numerical expression is seen as being proximate to the queried interval. With near query we can obtain those expressions of time if cb is even then 12: B, L ← calcBigminLitmax([T 1 .X, T 2 .X], [T 1 .Y, T 2 .Y], 1)13:else 14: B, L ← calcBigminLitmax([T 1 .Y, T 2 .Y], [T 1 .X, T 2 .X], 0) 15: rangeSearch(T 1 , L, H) ⊲ split 16: rangeSearch(B, T 2 , H) ⊲ split 17:return H Algorithm 2: Compute minimal set of z-order hashes. and numbers that may not intersect the queried interval but are in its neighborhood.The range-based query predicates can be combined by adding or removing hashes to be searched in the index. For instance, if we would like to have a result set for a intersect query that only contains results that overlap without any subsumption, we can compute the set of hashes for containedBy and contains and remove them from the set of hashes for intersect. This can be computed by the query processing engine without the need to scan the index. The only parameters required are the overall ranges of temporal and numerical expressions in the document collection and the precision of the stored z-order hashes.A naïve approach to process a query will be to perform a simple linear scan between pair of hashes corresponding to the query-MBRs. However, as noted earlier this may result in false positive results which can slow down the overall query processing. To reduce the number of spurious hits, we next describe three optimizations that can greatly speed up the overall query processing.Pruning Hashes for Invalid Subranges. First, based on the uncertainty-aware model, we can prune away those search subranges where the begin of the interval is greater than the end i.e., 𝑋 > 𝑌 . The hashes corresponding to these invalid subranges follow a recursive pattern. At the highest level of recursion, the entire bottom-right quadrant can be ignored along with two smaller triangles (see Figure 3 ). These triangles can be recursively broken down into smaller quadrants until the hashes covering the entire invalid area are found. The bottom-right quadrant is given by the hash 01 2 . Any value having this as its prefix is then invalid and can be ignored. The number of ignored values at each recursion level thus grows at a rate of 2 𝑛 , where 𝑛 is the current recursion level (with the initial level at 0). These values can be pre-computed and stored in a lookup-table for pruning during query processing. The total number of ignored values for a given level of precision is then:2 𝑛 + 2 𝑛-1 + 2 𝑛-2 + ... + 2 0 = 𝑛 𝑖=0 2 𝑛-𝑖 = 2 1+𝑛 -1.Adjusting Accuracy. Second optimization that we perform is to reduce the precision of the z-order curve while still being within a minimum range accuracy. The accuracy of representing a single dimension on the z-order curve is given by Equation 4. Solving that equation for 𝑛 and rounding up to the nearest integer gives the minimum number of bits needed to be certain that any hashes calculated are not deviating more than the allowed maximum for that dimension. This can be restated as:(𝑒 -𝑏 ) /2 𝑛 ≤ Deviation (5)As the range search is done over two dimensions, the calculated precision must be multiplied by two. If the dimensions differ in required accuracy, the precision required for the most accurate of the dimensions is used. The calculated number of bits is only the maximum precision needed and can be lowered for continuous hashes (discussed next). For larger ranges, potentially more hashes will be returned from the z-order curve, as the MBR may cover multiple quadrants at different precision levels. At the same time, searches over larger areas often require less precision to begin with. For example, if queried interval lies in the range of [1900, 1999] , having a potential ±10 year deviation in each end is not of great concern, compared to if the query was [1990, 1999] . This is utilized by defining the maximum allowed deviation as a part of the query processing. A larger range allows for a greater deviation, while a smaller range requires a smaller deviation. By dividing the smallest of the ranges by 10, a 10% deviation is achieved in the worst case. For instance, [1900, 1999] would then potentially allow for a ±10 year accuracy, while [1990, 1999] a ±1 year accuracy.Continuous z-order Values. Third optimization that we perform is to convert the computed query-MBRs to a minimal set of hashes to query the inverted indexes. Specifically, we utilize a modified variant of bigmin and litmax method [34] that does not need to consult the inverted indexes for the minimal hash set computation. This method takes as input the overall search range depicted by the query-MBR (i.e., coordinates of the diagonally opposite corners of the MBR) and recursively splits the search space into sub-ranges verifying if z-order hash is continuous. The notion of continuity here conveys if the hash is relevant to the search range or not. The basis condition of recursion is reached when maximum precision is obtained for the z-order hash. To determine continuity we check if two hash values are continuous by determining the number of common MSBs using a bitwise XOR. Every pair of common bits in the count represents if the hash values lie in the same quadrant. By counting such pairs of common bits we can determine the common parent quadrant the hash values occupy. Having counted the common bits, a further verification is done to see if both the hash values are same (either all 0s or all 1s based on the corner of the diagonal) after the number of common bits to ensure they indeed lie in the same quadrant. Otherwise, this indicates a discontinuity and a split must occur. These optimizations together are described in Algorithm 2. The third optimization of checking continuity is done on line 2. If they are continuous, the search can stop, and the common MSBs can be added to the return hash set (line 5). The second optimization is applied between lines 7-9. There the method checks if the number of common bits is equal to the maximum precision. If true, the search stops at the current recursion as the two hashes are seen as equal for the given precision, and the common bits are added to the return hashes. If none of the above terminating conditions are reached, then a discontinuity has been discovered and a split needs to be made (lines [10] [11] [12] [13] [14] . The computation of this split is described next.If a discontinuity occurs then the search space needs to be split into sub-ranges. To this end, we compute the split using a modified variant of bigmin and litmax method [34] . The split in the search space can either be horizontal or vertical. This is decided by the number of common bits between the pair of hashes describing the query-MBR. If there are an even number of common bits then the next bit which is not common is a Y-value (horizontal). Similarly, if there are an odd number of common bits then the next bit is an X-value (vertical). We can readily identify the values for one of the dimensions in the new split as they are already known and can be extracted from the current corners of the MBR. A horizontal split means that the search is split along the Y-axis and that the current X-values are within the search space. The bigmin and litmax calculation is then done to find the Y-values just to the left and to the right of this split. Similarly, a vertical split means a split along the X-axis, and the calculation is done to find the X-values just to the left and to the right of the split. The computation takes the values of the known dimension as one pair, and the values of the unknown dimension as another. The values are the extracted bit representation of each dimension of the hashes, i.e., starting with the MSB and taking every other bit yields the Y-value for that hash. The calculation differs based on which dimension the calculations is to be done for. A horizontal split would then take in both X-values as the known pair, and the Y-values as the unknown pair, with the computation being done for the Y-dimension.The computation (shown in Algorithm 3) is straight-forward and requires appending a set of bits to the common MSBs of the values of the unknown dimension (lines 3-6). The common bits indicate where the dividing line of the split is. bigmin is the next (smallest) value within the search range in the upper part of the split. litmax is the largest value in the lower part of the split. bigmin's value for the unknown dimension is calculated by appending to the common bits. A 1 is appended to indicate the upper part of the split, followed by 0s such that it is the smallest value in this part. litmax's value for the unknown dimension is the inverse, appending a 0 followed by 1s. The final litmax and bigmin value is calculated by interleaving the values from the known dimension with the calculated litmax and bigmin values from the unknown dimension. litmax is interleaved with the largest of the known values, and bigmin with the smallest (lines 7-12). The starting value of the final hash is always the Yvalue and a dimension bit indicator shows which dimension is the unknown and which is known (line 7).In Figure 5a , we illustrate how the range search is divided into smaller sub-ranges. The two-dimensional range search is done from point 𝑆 to point 𝑇 equals a z-order range search from the hash in quadrant 25 (011000 2 ) to the hash of quadrant 54 (110101 2 ), over a 6-bit z-order curve (only the four-bit hashes are shown). 𝑆 and 𝑇 are not continuous, as shown by the quadrants shaded red. The algorithm finds the number of common bits, which is zero, meaning a horizontal split and unknown Y-values. The extracted Y-bits from quadrant 25's hash is 010 2 and from quadrant 54 100 2 . As the current Y-values share no common bits, the Y-bits for bigmin (the bigmin mask) is simply 100 2 and for litmax 011 2 . Interleaving 100 2 with the (known) X-bits of quadrant 25 (100 2 ) results in a bigmin of 110000 2 , which is in quadrant 49. Similarly, interleaving 011 2 with the X-values of quadrant 54 (111 2 ) yields a litmax of 011111 2 (quadrant 32). Based on these values, the search range is split into two sub-ranges shown by the red line in Figure 5a . The new ranges are quadrant 25 to quadrant 32 and quadrant 49 to quadrant 54. The search from quadrant 25 (01100 2 ) to quadrant 32 (011111 2 ) is done in the same manner. However, this time the range is continuous. The hashes share three common bits, with the one diagonally opposite corner's hash having all zeroes following the common bits, and the other's hash having all ones. No further searching is then needed, and the hash (011 2 ) is added to the result hashes. The same does not apply for the search from 49 to 54, as the quadrants 51 and 52 are outside the search range, but between the z-order interval. The number of common bits between quadrants 49 and 54 is three (110 2 ), indicating a vertical split and unknown X-values. The X-bits of quadrant 49 are 100 2 and 111 2 for quadrant 54. They share one common bit, resulting in a bigmin mask of 110 2 and a litmax mask of 101 2 . Interleaving the bigmin mask with the Y-bits of quadrant 49 (100 2 ) yields the bigmin value 110100 2 (quadrant 53). Similarly, interleaving the litmax mask with the Y-values of quadrant 54 (100 2 ) yields 110001 2 (quadrant 50). The new search ranges are then from quadrant 49 to 50 and from 53 to 54. The split is indicated by the blue vertical line in Figure 5a . Both these new ranges are found to be continuous as they share common bits, followed by all ones and all zeroes. The hashes added to the result are then 110002 and 11010 2 . However, nash will only allow continuous ranges which have an even bit length, such that the prefix properties can be utilized in a base 4 encoding. This would result in two further vertical splits, and the hashes for 49, 50, 53, and 54 would be added individually. Figure 5b shows the different levels of the search in a quadtree. Only the visited subtrees are included. The red lines illustrate the first range split, and the blue  
evaluation: 
 We next describe the evaluation setup for our experiments. Annotated Document Collections. We instantiate indexes for four document collections. The first document collection we use is the New York Times Annotated corpus [7] which consists of news articles published the New York Times between the period 1987 to 2007. This document collection consists of approximately 1.8 million documents. The second document collection is the complete English Wikipedia [1] , which consists of the collaboratively authored documents regarding notable entities and events. A recent snapshot of the entire English Wikipedia comprises of around 6.34 million documents. The third document collection we use is a news subset of the English Common Crawl, published as C4 [30] . This document collection consists of approximately 13.81 million documents. The fourth and final document collection we use is the entire C4-En corpus derived from the English Common Crawl. This is the largest collection in our evaluation setup amount to more than 365 million documents. We annotated each document collection using the Stanford's CoreNLP toolkit [25] for coarse-grained named entities and resolved temporal and numerical expressions. The temporal and numerical expressions were then mapped to our z-order based hashes. Complete statistics regarding the document collection statistics are given in Table 1 .Implementation and Indexes. We implemented the entire codebase for the indexing infrastructure from ground up in Java. The z-order hashes for temporal expressions were done with 40-bit precision so as to accommodate the hierarchical property of z-order curves. With 40-bit precision, we can query temporal expressions precisely at the day-level granularity. The z-order hashes for numerical expressions were done at 20-bit precision to accommodate large global numerical ranges. The z-order indexes store both the hashes of the temporal and numerical expressions along with their prefixes to leverage the hierarchical properties of the space-filling curves. In order to process event-oriented queries, we created a suite of indexes over the word layer, the coarse-grained named entity layer, and the z-order hashes of the resolved values of temporal and numerical expressions as discussed in Section 2.3. Due to the size of the C4-En collection, we only instantiate unigram and bigram indexes for locating n-grams. Moreover, we omit the annotation only indexes for C4-En as the posting lists for a very small coarse-grained named entity vocabulary grow prohibitively long. Similarly, to reduce the size of C4-En direct index, we only store the word layer along with two other sentence-level annotations.The document collections were pre-processed, annotated, and indexed on our Hadoop cluster of twenty five machines. Each machine in the cluster consists of the following minimal specifications: an Intel Xeon CPU with 16 cores and processing speed of 2.20 GHz and 128 GB of physical memory. The indexes are stored in HBase, a scalable distributed key-value store, which runs on our Hadoop cluster. HBase provides fault-tolerance and allows us to scale our query processing over millions of documents with ease. A summary of the indexes that we have created with their sizes are shown in Table 2 . All our experiments were carried out on a compute node that is part of the Hadoop cluster.Query Testbed. To construct a testbed of event-oriented queries, we extracted important historical event descriptions for each day of the year from the New York Times Learning Network -"On This Day" portal [5] . Each event-oriented query in the testbed contains combinations of annotations and the textual surface forms. For each query, we ensure that each query has at least one coarsegrained named entity and at least one temporal expression (i.e., its event date). In total, we have 4,548 queries with approximately 2.50 coarse-grained named entities (i.e., person, location, organization, and misc.) on average per query and approximately 1.54 temporal and numerical expressions on average per query. As an example, for the event: "April 17, 1961, about 1,500 CIAtrained Cuban exiles launched an invasion at the Bay of Pigs on the southwestern coast of Cuba in a failed attempt to overthrow Fidel Castro" [5] . The corresponding event query in the testbed is: {(April 17, 1961)⊕([1961-04-17 , 1961-04-17]), (1,500)⊕(∼1500.0), (cuban)⊕(misc),(bay of pigs)⊕(loc.), (cuba)⊕(loc.), (fidel castro)⊕(person)}. Where, ⊕ shows the combination of the word sequences corresponding to the named entity annotations.Setup. We evaluate our system and the baselines for end-to-end query processing runtimes. To do so, we sample 100 queries from the testbed and run them three times with cold-cache setup. Coldcaches are simulated by shuffling the queries in between rounds. We report here results based on cold-cache settings as the results are similar to that of warm-cache setup. We issue each event-oriented query along with their event date. We evaluate each query in the sample as a conjunctive query, i.e., the matched documents must contain all the coarse-grained named entities with its event date and accompanying numerical and temporal expressions. We further evaluate the effect the query optimizations have on nash by varying the search accuracy by 5%, 10%, and 25%.Baselines. We first establish a naïve baseline of the total time required to perform a distributed scan over the document collections on our Hadoop cluster. With the scan baseline, we obtain a worst case bound on query runtimes. We further compare our system to two additional baselines: texti and anni. The texti baseline processes a query by first identifying a candidate set of documents corresponding to the event coarse-grained named entities by retrieving the results using their phrases from the word layer. The texti baseline then ensures that the candidate set of documents indeed contain the event date and accompanying temporal and numerical values by referring to the resolved annotation layers for each of the candidate documents by using the direct index. The anni baseline, works similar to the texti baseline but differs in how it matches the temporal and numerical expressions. The anni baseline, identifies potential matches for the event date and accompanying temporal and numerical expressions by using an inverted index over coarse-grained named entity annotation layer. Having identified the potential matches, it ensures that the resolved values for the coarse-grained named entities are indeed correct using the direct index. Note that the anni baseline is functionally similar to a baseline utilizing indexes over numerical intervals. This baseline would be slower than anni as it would entail scanning the interval indexes multiple times for the range search predicates. For the C4-En collection, evaluating the baselines texti and anni is prohibitively expensive as it may entail scanning the entire document collection using the direct index. Thus, for the C4-En collection we provide comparative results using the distributed scan baseline (scan). We evaluate two variations of our proposed system: nash and nash-opt. Both variations of our proposed system, nash and nashopt, utilize only the z-order based indexes to match the event dates and the accompanying temporal and numerical expressions. For nash we disable the query optimizations and ensure that sets of hashes generated are at full precision for retrieval of temporal and numerical expressions. While for nash-opt we leverage the query optimizations that further adjust the accuracy (deviation set to 1%) during query processing. We evaluate both the baselines and our system for all four of the range-based search predicates: contains, containedBy, intersect, and near (Δ = 0). A summary of the indexes the systems utilize is given in Table 3 . As the baselines, texti and anni, utilize the direct indexes we can ensure that the results sets obtained are equivalent to nash. However, when applying the additional optimizations during query processing for nash-opt, e.g., adjusting accuracy, we may obtain additional matches that contain temporal and numerical ranges in the proximity of queried intervals.× × × × texti • × × • anni • • × • nash • × • × nash-opt • × • ×Distributed Scan Results for each of the four document collections are shown in Table 4 . As can be seen the time taken for scanning each collections is proportional to its size. For Wikipedia the time taken is more than C4-News (even though it is larger than Wikipedia). This is because Wikipedia documents are longer than the documents contained in C4-News archive. The average number of words per document for Wikipedia is approximately 600.95 words as compared to 444.61 words per document for C4-News. For New York Times, Wikipedia, and C4-News the distributed scan over our Hadoop cluster can be done in the order of several minutes. For the Web-scale English C4-En collection, the distributed scan 5 , we observe that their runtimes are in the same neighborhood of minutes for New York Times, Wikipedia, and C4-News document collections.End-to-End Runtime Results of our experiments are reported in Table 5 . We first discuss the results for the range-based query predicates containedBy and intersect. These predicates are challenging for nash to compute as they require computing query-MBRs for temporal and numerical expressions that can subsume (containedBy) or intersect the queried intervals. The results for the range-based query predicates containedBy and intersect show our system nash outperforms the texti baseline by a factor in the range of 15.46 -17.86× for the New York Times document collection. For Wikipedia, which contains the most number of temporal and numerical expressions, and C4-News our system outperforms the most competitive baseline texti by a factor in the range of 2.71 -11.01×. This speedup can be attributed to the fact that the texti baseline needs to consult the direct index for each document in the candidate result set to ensure that the predicate conditions of each of the range-based search operations are satisfied. When comparing our system nash to anni baseline our system performs 3.24 -16.45× faster for containedBy queries and 3.21 -15.98× faster for intersect queries. This speedup can be attributed to smaller posting lists corresponding to the z-order hashes as compared to lengthier posting lists corresponding to coarse-grained named entities types of number and date. Therefore, it takes longer for the anni baseline to process a conjunctive event-oriented query. Whereas, for nash multiple hashes corresponding to the query-MBR can help prune irrelevant documents early in the query processing. When further adjusting for accuracy, we can further lower our runtimes with nash-opt and obtain speedups in the range of 15.14 -22.38× for containedBy predicate and 14.20 -20.80 × for intersect predicate. Also, we observe that nash-opt significantly reduces the query runtimes for Wikipedia, which contains the maximum average number of temporal and numerical expressions per document.We next discuss the results for the range-based query predicates contains and near. These predicates are more probable to be requested by users such as journalists and scholars in digital humanities as they enable a proximity and containment search around a query interval. The results for the range-based query predicates contains and near show that nash, provides speedups in the range of 41.23 -51.30× when compared to the texti baseline for the New York Times collection. For Wikipedia and C4-News, we obtain speedups in the range of 28.87 -35.16× for contains queries and speedups in the range of 19.23 -29.75× for near queries. When comparing our system nash to anni baseline, our system performs 36.10 -53.10× faster for contains queries and 24.30 -42.74× faster for near queries. Again, the speedup in this case can be attributed to the larger posting lists associated with coarse-grained named entities when compared to the posting lists for z-order indexes. Overall, for nash we observe that it is quicker to execute the queries corresponding the predicates contains and near when compared to executing same queries with the predicates containedBy and intersect. This is because the number of hashes needed to describe the query-MBRs for contains and near queries are fewer than those needed to describe containedBy and intersect. When further adjusting for accuracy using nash-opt we observe a less significant improvement. This can be attributed to the observation that a set of more precise (longer) hashes are required for proximity queries when compared to intersection queries and therefore are least affected by the adjustment for accuracy. Overall, for nash-opt, we see speedups in the range of 29.55 -62.04× for contains and 18.66 -46.51× for near queries.For the C4-En document collection, we draw comparative results based on the scan baseline. As we have seen before, the scan baseline is competitive for the task of range search and performs similarly when comparing to texti and anni that leverage n-gram and annotation indexes for the smaller three document collections. We observe that nash provides a speedup in the order of 23.18 -24.22× for the containedBy and intersect query predicates over scan. While nash-opt provides a speedup in the range of 27.54 -28.08× for the same query predicates. For the query predicates contains and near, nash provides speedups in the range of 43.57 -46.40× over scan. Whereas nash-opt provides speedups in the range of 43.66 -46.78× for contains and near query predicates. These speedups are similar to the speedups for other collections in our evaluation setup and thus demonstrate that our system nash can reliably scale to the Web for event-analytics.End-to-End Runtime Results by Adjusting Accuracy. We further evaluate nash-opt for end-to-end query execution by adjusting for accuracy (see Table 6 ). To that end, we execute the same sample of 100 queries in cold cache setup while setting deviations of 5%, 10%, and 25% in search accuracy of the ranges (see Equation 5). We first discuss the results for the query predicates containedBy and intersect. We observe that as we increase the deviation, the runtimes overall increase across the document collections. We see the most significant increase in runtimes when executing the queries with deviation at 25%. The trend of increasing runtimes with increasing deviation percentages can be attributed to shorter hashes that describe the query-MBRs. As discussed in Section 2.5, shorter hashes correspond to larger search regions that intersect a larger number of temporal and numerical expressions when compared to longer hashes (indicative of higher search accuracy) that describe a precise search region referring to only the required intervals. This is because they describe a larger search region that subsume and intersect the query interval (see Figure 3c ). Since, the query predicates containedBy and intersect require looking up of such shorter hashes as compared to the query predicates contains and near they consume more time as the deviation is increased.We next discuss the results for the query predicates contains and near. For these query predicates, we observe that as we increase the deviation percentage the overall query execution time decreases marginally. The insignificant decrease query runtimes can be attributed to three factors. First, contains and near query predicates implicitly require longer hashes to describe the neighborhood of the search region and thus are least affected by the reduction in the search accuracy. Second, for the proximity-based queries since the search region is described by longer hashes it entails lookup of shorter posting lists of temporal and numerical expressions. Third and finally, the deviation in search accuracy has a more pronounced effect when indexing temporal and numerical hashes with a higher-precision z-order curve. Such a requirement may arise when indexing financial documents containing a higher number of numerical expressions located closer to to each other in the search space. For Web search, where temporal and numerical expressions are less densely located in the search space a lower-precision z-order curve is sufficient and may provide reliable performance.Index Sizes. nash utilizes z-order indexes that are a factor of at least 1.90× and at most 2.05× smaller than storing the direct index. For extracting text regions corresponding for event-oriented queries, we need to only maintain a smaller direct index that records only the word layer. For instance, the C4-En z-order indexes are 4.01× smaller than the direct index, where fewer layers are stored. 
related work: 
 Earliest works in search and indexing using space-filling curves are [23, 34] . Tropf and Herzog [34] showed that query processing using z-order curves results in a logarithmic speed up with the number of indexed records. Lawder and King [23] demonstrated methods for utilizing space-filling curves for multi-dimensional indexing. Their approach, which is similar to the bigmin and litmax method [34] , utilized Hilbert curves to implement a search infrastructure with three dimensions.Space-filling curves have found wide applicability for indexing geo-spatial data as demonstrated in several works and publicly available systems [2-4, 15, 20, 24, 27, 35, 37] . Examples of systems leveraging space-filling curves are GeoWave [35] and MD-HBase [27] . Both GeoWave and MD-HBase utilize space-filling curves to index geo-spatial data over distributed key-value stores to speed up query processing. geohash.org [2] is a publicly available API that allows users to represent latitude and longitude pairs into base-32 z-order hashes (geohashes). Similar approaches have been widely adopted in open-source NoSQL database systems such as ElasticSearch [3] and MongoDB [4] . A more recent work [24] combines both these threads of research. Lee et al. [24] show how to index geo-spatial data using geohashes in HBase such that it can support the fundamental spatial query operations. The authors are able to perform these spatial operations by leveraging the hierarchical characteristics that geohashses implicitly model. Prior works on combining spatial and text search has resulted in approaches that combine spatial indexing methods such as R-Trees with inverted indexes over words [15] . However, such approaches are less flexible and not scalable as there is redundant storage of location-based data for each word in the collection. Similarly, prior works such as [37] present approaches that do not support complete set of range-based operations and rely only on efficient top-k query processing based on proximity scores.Earlier works on range-based search in uncertain metric-spaces [16] , interval-based data [9] , and temporal databases [22] all rely on B + -trees as their underlying data structure which can not immediately be utilized in large-scale search infrastructures that primarily rely on inverted indexes for query processing. In [12] , the authors index versioned document collections, where versions correspond to timestamps. They utilize a partition-based approach to split posting lists corresponding to different timestamps enabling quick execution of timepoint-based queries. While in [8] , the authors propose a query optimization framework to extend querying to time intervals with an additional I/O constraint to retrieve a subset of the relevant result set using hash-based KMV synopsis. A comprehensive survey of semantic search using text and knowledge graphs [10] shows that most storage techniques for annotated document collections ignore to support advanced capabilities for document retrieval that contain temporal and numerical expressions. Even modern transformer-based large language models fall short of learning semantics of numbers present in large document collections [31] . 
conclusion: 
 We described nash, a search system that provides the capability to perform range-based search over intervals that can be implicitly contained within natural language expressions of time and numbers. To do so, nash utilizes z-order curves that enable us to search for intervals at different levels of granularity. Furthermore, we described the concept of continuous hashes and an improved optimization based on the bigmin and litmax approach to speedup the query processing. Our results show that nash provides impressive speedups in the order of 19.23 -53.10× for more probable contains and near queries. Moreover, nash provides these speedups by utilizing z-order indexes that are 1.90 -2.05× smaller than the direct index required otherwise. 
 
 Appendix:  


Decision: The paper proposes the combination of keyword-based search with the search for temporal and numeric interval expressions. It applies existing methods for resolving temporal/numeric expressions from text, and uses z-order hash indexes for supporting search with basis on temporal/numeric restrictions (which are seen as intervals in a 2D Cartesian space). 

The innovative contributions relate to optimizations in query processing with z-order indexes, and to the combination of z-order hashes with functionalities for keyword-based search (i.e., both the z-order hashes and the keywords are stored in a common index associated to inverted lists), aiming at high speedups in query processing, and small index size.

The methods advanced in the paper are perhaps closer to the area of "databases", instead of "information retrieval", as for instance "relevance" and "ranked retrieval" are not considered as part of the evaluation criteria. However, I also believe that this particular aspect of relevance can be somewhat subjective, and this meta-review mostly attempts to follow the objective comments supported by falsifiable evidence. Still, with basis on the somewhat limited depth of the novel contributions that are provided, I am recommending that this manuscript can perhaps be accepted as a poster.

The experimental results are interesting, but ideally the authors should consider more queries in the tests (which should be easy, since there is no need to collect relevance judgements in order to measure speedups) and also comparisons against other approaches (e.g., in the databases literature, there are actually several proposals of data structures to simultaneously index/search over 2D intervals and text).

Reviewer LFQN provides relevant and interesting feedback that can be considered for improving the manuscript, and reviewers 7xh4 and em64 make good points about how the proposed contributions should have a stronger relation to the general area of "information retrieval."

Reviews: review: main_review: main_review: The paper clearly considers an important and underexplored topic. Efficiently managing temporal and numeric expressions in context of search engines is vital for certain applications, and the paper provides some useful examples for information needs that would benefit from temporal query operators. The paper builds on existing work in terms of the annotation of temporal expressions, the underlying model for representing uncertain temporal expressions, and z-order curves for indexing arbitrary intervals and points. The actual contribution of the paper is the resulting system, which comes with well-designed indexes that smoothly integrate temporal operators with entity and keyword based query expressions. The paper cleverly explores options for improving standard z-order hashes, which helps to further optimize query processing. 

The experimental evaluation is adequate, with four collections of different size (both in terms of number of documents and size of documents) and content. Experiments are done with only 100 queries, which is not very much for experiments regarding efficiency where the possible queries are not constrained by the availability of relevance assessments. It is unclear why the paper initially reports 4,548 queries, out of which only 100 are used for the actual experiments. Baselines are reasonable; the scan-based method is clearly a very naive baseline that would usually not be applied within the context of a search system, but gives an idea of worst-case times. 

The demonstrated query processing times are impressive, especially as they were not achieved with a highly tuned in-memory framework. Response times of a few seconds for such large collections are fully adequate for most applications. Compared to the performance of NASH alone, the additional improvements with the optimizations are rather small.

The paper does not report very well how the actual implementation was done. It reports some details regarding the Hadoop-based implementation and the HBase-based index storage, but more details regarding how indexes were represented in HBase would have been useful. The paper would clearly be more valuable if the source code for the system, ideally together with queries and detailed experimental results, was made available.

The paper clearly puts its focus on the NASH system, and as a system paper, I consider it useful and interesting. It is not so clear to me, however, how it matches the more theory-oriented theme of ICTIR, especially as the contributions are on the systems side and not so much on the underlying model (which existed before and are reused). This is the main weakness of an otherwise good paper.
main_review: main_review: The paper is well-written and well-organised. The topic is interesting and related to ICTIR.
main_review: main_review: The paper is well written and easy to follow.
main_review: main_review: This paper takes a typical database approach to the problem of combining exact text match with range search, as relevance and ranking are not an issue here. Spatial data structures (for which range search and intervals are the most simple case) have been investigated in the database community since the mid-1980s. Unfortunately, it does not become clear where this paper adds anything new to this area (besides the improvement of an older optimization method).
Today's experimental data sets may be bigger and the information extraction methods are substantially better than in the last century, but apart from having better test collections, I cannot see any scientific progress in this paper.