text:
Efficient set intersection for inverted indexing
- Zoe Day
- 3 years ago
- Views:
1 Efficient set intersection for inverted indexing J. SHANE CULPEPPER RMIT University and The University of Melbourne and ALISTAIR MOFFAT The University of Melbourne Conjunctive Boolean queries are a key component of modern information retrieval systems, especially when web-scale repositories are being searched. A conjunctive query q is equivalent to a q -way intersection over ordered sets of integers, where each set represents the documents containing one of the terms, and each integer in each set is an ordinal document identifier. As is the case with many computing applications, there is tension between the way in which the data is represented, and the ways in which it is to be manipulated. In particular, the sets representing index data for typical document collections are highly compressible, but are processed using random access techniques, meaning that methods for carrying out set intersections must be alert to issues to do with access patterns and data representation. Our purpose in this paper is to explore these tradeoffs, by investigating intersection techniques that make use of both uncompressed integer representations, as well as compressed arrangements. We also propose a simple hybrid method that provides both compact storage, and also faster intersection computations for conjunctive querying than is possible even with uncompressed representations. Categories and Subject Descriptors: E.2 [Data Storage Representations]: Composite structures; H.3.2 [Information Storage]: File organization; H.3.3 [Information Search and Retrieval]: Search process Additional Key Words and Phrases: Compact data structures, information retrieval, set intersection, set representation, bitvector, byte-code 1. INTRODUCTION The computation of set intersections is essential in information retrieval systems. The dominant indexing data structure leveraged by search engines is the inverted index [Witten et al. 1999; Zobel and Moffat 2006]. In an inverted index, an ordered set of document identifiers referred to as an inverted list or postings list is stored for each term that appears in the collection, identifying which documents contain the term. These lists are then processed via conjunctive Boolean queries in order to identify the subset of documents which contain all of a given set of search terms the conjunction, or intersection of the sets indicated by the lists. The literature describes a range of techniques for computing set intersections, falling Authors addresses: J. Shane Culpepper, School of Computer Science and Information Technology, RMIT University, Victoria 3001, Australia. Alistair Moffat, NICTA Victoria Research Laboratory, Department of Computer Science and Software Engineering, The University of Melbourne, Victoria 3010, Australia. The work described in this paper was presented in preliminary form at the 14th SPIRE Symposium on String Processing and Information Retrieval, Santiago, November 2007; and at the 12th ADCS Australasian Document Computing Symposium, Melbourne, December National ICT Australia (NICTA) is funded by the Australian Government s Backing Australia s Ability initiative, in part through the Australian Research Council. ACM Journal Name, Vol. V, No. N, Month 20YY, Pages 1 24.
2 2 J. Shane Culpepper and Alistair Moffat broadly into two groupings: approaches that assume that the set are stored as sorted arrays of integers, and thus that the d th integer in the list can be accessed in O(1) time; and approaches that assume that the lists are stored and accessed sequentially, possibly in some compressed form, and thus that accessing the d th integer in the list might take time that grows as a function of d, even if it is sublinear in d. Our presentation in this paper first explores the execution and cost of methods based around these two quite different starting points, and evaluates their relative performance, assuming throughout that all of the required data is being held in random-access memory. We then re-visit a third set representation, one that is usually dismissed as being inordinately expensive for storing index data, but one that with judicious balancing of concerns provides a notable speed up of set intersection operations, without adding greatly to the overall cost of storing the index. We limit our investigation to in-memory indexes in order to provide a clean abstraction for our efficiency evaluation in a manner similar to other recent empirical investigations [Strohman and Croft 2007; Transier and Sanders 2008]. The next section lays the foundation for all three of these approaches, by describing the underlying operations required of all set data structures. 2. SET OPERATIONS AND SET INTERSECTION There are two broad categories of operations on sets. Operations which return information derived from the current state of a set are referred to as query operations, and operations which change the contents or state of a set are update operations. 2.1 Dictionaries and Sets The dynamic dictionary abstract data type assumes that two update operations and one query operation must be supported: INSERT(S, x) Return the set S x. DELETE(S, x) Return the set S x. MEMBER(S, x) Return TRUE, and a pointer to x if x S; otherwise return FALSE. The simpler static dictionary does not require the two update operations, but does require that a suitable initialization process be provided that creates a queryable structure from a list of the set s members. Such bulk load processes are usually more efficient than a sequence of INSERT operations would be. When the objects being stored in a static dictionary are integers, one simple representation of a static dictionary is as a sorted array of explicit values, referred to in this work as the SAEV set representation, where explicit means that each ordinal integer is stored in unmodified form, independently of the others in the set. The MEMBER operation over a set of n items stored in SAEV format can be implemented in O(log n) time using binary search. Dictionaries are often used to build more elaborate data structures which support composite set operations that typically manipulate multiple elements in a single atomic operation, and are constructed using one or more of the elemental operators listed above:
3 INTERSECT(S, T) Return the set S T. UNION(S, T) Return the set S T. DIFF(S, T) Return the set S T. EQUAL(S, T) SPLIT(S, x) RANGE(S, x, y) Efficient set intersection for inverted indexing 3 Return TRUE if S = T, otherwise return FALSE. Return the two sets {z z S and z x} and {z z S and z > x}. Return the set {z z S and x z < y}. Note that the SPLIT and RANGE operations assume that the set is ordered, and that comparisons may be performed on the items being manipulated. If an ordering requirement is added, several more primitive operations can be considered, including a finger search mechanism: PRED(S) SUCC(S) Return a pointer to the element in S that immediately precedes the current one. Return a pointer to the element in S that immediately follows the current one. F-SEARCH(S, x) Return a pointer to the least element z S for which z x, where x is greater than the value of the current element. RANK(S, x) Return {z z S and z x}. SELECT(S, r) Return a pointer to the r th largest element in S. In inverted index processing, the INTERSECT, UNION, and DIFF operations can be implemented using F-SEARCH, PRED, and SUCC operations. The latter three operators are state-modifying, in that they require that a current element have been determined by a previous operation, and in turn move that designator to a different element as a side effect of their execution. As the sequence of operations unfolds, the locus of activity shifts through the set being processed. In some representations, these operations can in turn be built on top of RANK and SELECT. For instance, SUCC(S) can be implemented as SELECT(S, 1 + RANK(S, c)), where c is the current item. 2.2 Binary Intersection of Ordered Sets The INTERSECT operation is the critical one involved in conjunctive Boolean query processing; and also in ranked query processing when the ranking is a static one, based on fixed attributes of the page, with all presented answers required to contain every query term [Zobel and Moffat 2006]. To resolve these queries, the document collection is preprocessed to generate a set of inverted lists, in which each term is represented by an ordered set of ordinal document numbers in which that term appears. To process a conjunctive Boolean query q containing q terms, a q -way intersection of q pre-computed sets is then required. The simplest case is when q = 2, and two sets are to be intersected; and the most obvious approach is to spend O( S + T ) time on a standard sequential merge, picking out the elements in common to the two sets via a loop in which a single comparison is made at each iteration, and depending on the outcome of the comparison, a SUCC operation is applied to one or the other of the two lists. This approach is the correct one for UNION operations, in which the size of the output list is O( S + T ) and it is assumed that the two
4 4 J. Shane Culpepper and Alistair Moffat Algorithm 1 Binary set intersection INPUT: Two ordered sets S and T, with S = n 1 and T = n 2, and n 1 n 2. OUTPUT: An ordered set of answers A. 1: A { } 2: x FIRST(S) 3: while x is defined do 4: y F-SEARCH(T, x) 5: if x = y then 6: APPEND(A, x) 7: end if 8: x SUCC(S) 9: end while 10: return A input sets may not be destroyed during the operation, but is not efficient for INTERSECT in the cases when S T. Algorithm 1 describes a more complex but also more efficient intersection algorithm, in which each element of the smaller set, S, is tested against the larger set, T, and retained if it is present [Hwang and Lin 1972]. The search retains state as it proceeds, with the eliminator element, x, stepped through the elements of S; and the F-SEARCH (finger search) operation used in T to leapfrog over whole subsequences, pausing only at one corresponding value in T for each item in S. An auxiliary operation, FIRST, is used to establish an initial state in S; and T is implicitly assumed to have also been initialized, so that the first F-SEARCH starts from its least item. The essential primitive operations in Algorithm 1 are SUCC and F-SEARCH, with S of each performed. In fact, the SUCC operation in set S can be replaced by a symmetric call to F-SEARCH(S, y) if SUCC is not available as an operation, but the expected number of elements jumped is just one, and in practice SUCC is likely to execute faster than F-SEARCH. A range of ways in which F-SEARCH can be implemented is discussed in the next subsection, and SUCC can for most purposes be assumed to require O(1) time. 2.3 Algorithms for Efficient F-Search Binary search over n 2 elements requires 1+ logn 2 comparisons, and if set T is stored as a sorted array of explicit values (SAEV format), then binary search can be used to underpin the F-SEARCH operations required in Algorithm 1. In particular, binary search is the optimal approach when S = 1. As a slight improvement, the current element in T can be used to delimit the search, to gain an incremental benefit on the second and subsequent F-SEARCH calls. There are also other searching methods that can be applied to SAEV representations, including linear search, interpolation search, Fibonacci search, exponential search (also referred to as galloping search by some authors), and Golomb search [Hwang and Lin 1972]. The desirable characteristic shared by these alternatives is that the search cost grows as a function of the distance traversed, rather than the size of the array. For example, linear search requires O(d) time to move the finger by d items; and as is described shortly, exponential search requires O(log d) time [Bentley and Yao 1976]. A sequential linear
5 Efficient set intersection for inverted indexing 5 Algorithm 2 Golomb F-SEARCH INPUT: A sorted list L of n elements, a pre-calculated Golomb parameter b, a search key x, and a current position in L indicated by curr. OUTPUT: An offset in the sorted list L if x is found, the offset of the successor of x if not found, or ENDOFLIST if x is greater than L[n]. 1: pos curr + b 2: while pos < n and L[pos] < x do 3: curr pos 4: pos curr + b 5: end while 6: if pos > n then 7: pos n 8: end if 9: offset BINARY-SEARCH(L[curr pos], pos curr, x) 10: if offset = ENDOFLIST then 11: curr pos 12: else 13: curr pos + offset 14: end if 15: if curr > n then 16: return ENDOFLIST 17: else 18: return curr 19: end if merge dismissed above as being inefficient when n 1 n 2 results if linear search is used in Algorithm 1. In situations when 1 n 1 n 2, use of exponential search in the F-SEARCH implementation is of considerable benefit. In an exponential search, probes into T are made at exponentially increasing rank distance from the current location, until a value greater than the search key is encountered. A binary search is then carried out within the identified subrange, with this halving phase having the same cost as the doubling phase that preceded it. In this approach each F-SEARCH call requires log d comparisons, where d is the difference between the rank of the finger s previous position and the new rank of the finger pointer. Over n 1 calls for which n 1 i=1 d i n 2, the convex nature of the log function means that at most O(n 1 + n 1 log(n 2 /n 1 )) comparisons are required. Note that this approach has the same worst case asymptotic cost as using binary search when n 1 is O(1), and has the same worst case asymptotic cost as linear search when n 2 /n 1 is O(1). If average comparison cost is of interest, the F-SEARCH can make use of the interpolation search mechanism [Gonnet et al. 1980]. This searching algorithm has an average execution cost of O(log log n) when the data is drawn from a uniform distribution, but in the worst case might require n comparisons. In practice, the running time of interpolation search is often worse than binary search, because each comparison involves more associated computation and hence more time. However, modern processors are closing the gap between interpolation and binary search, and complex calculations are becoming cheaper than navigating across cache lines [Hennessy and Patterson 2006].
6 6 J. Shane Culpepper and Alistair Moffat Algorithm 3 Small versus small intersection, svs INPUT: A list of q ordered sets S 1...S q. The function INTERSECT is defined in Algorithm 1. OUTPUT: An ordered set of answers A. 1: without loss of generality assume that S 1 S 2 S q 2: A S 1 3: for i = 2 to q do 4: A INTERSECT(A, S i ) 5: end for 6: return A The F-SEARCH algorithm can also be based on Golomb searching, in a mechanism described by Hwang and Lin [1972]. Algorithm 2 shows an implementation of this technique. Search proceeds in a manner somewhat similar to exponential F-SEARCH, but with a fixed forwards step of b items used at each iteration. Once overshoot has been achieved, a binary search takes place over the (at most) b items that have been identified. When searching through a set of size n 2 for the elements of a set of size n 1, the correct value for the step b is 0.69(n 2 /n 1 ), with a total search cost that is again proportional to O(n 1 + n 1 log(n 2 /n 1 )) [Gallager and van Voorhis 1975]. Variable-length integer coding techniques and F-SEARCH algorithms are duals of each other. For example, linear search is the dual of the unary code; binary search the dual of the binary code; the exponential search of Bentley and Yao [1976] is the dual of the Elias C γ code [Elias 1975]; and the search described by Hwang and Lin [1972] is the dual of the Golomb code [Golomb 1966]. Likewise, the search method of Baeza-Yates [2004] is the dual of the interpolative codes of Moffat and Stuiver [2000], and is conceptually similar to the divide and conquer merging techniques explored by Moffat and Port [1990]. Via this duality it is possible for any integer coding mechanism to be applied to the F-SEARCH task and then employed in an intersection algorithm on SAEV-representations. 3. MULTI-SET INTERSECTION When more than two sets are being intersected, the simplest approach is to iteratively apply the standard two-set intersection method using as a sequence of pairwise operations. Algorithm 3 shows this small versus small (svs) approach. The smallest set is identified, and then that set is intersected with each of the others, in increasing order of size. The candidate set is never larger than S 1 was initially, so the worst-case cost of this approach using a SAEV data representation using an F-SEARCH that takes O(log d) time to process a jump of length d is given by q i=2 n 1 log n i n 1 n 1 ( q 1)log n q n 1, where it is assumed that the sets are ordered by size, with n 1 n 2 n q. The svs method is simple and effective, and benefits from the spatial locality inherent from processing the sets two at a time. Even so, each different F-SEARCH implementation gives rise to a different svs computation. Other svs-based approaches are also possible. For example, the divide and conquer
7 Efficient set intersection for inverted indexing 7 binary intersection approach described by Baeza-Yates [2004] can also be iterated in a small-versus-small manner. 3.1 Holistic Intersection Algorithms The alternative to the svs approach is to combine all of the sets using a single concerted sweep through them all. The resultant holistic algorithms offer the possibility of being adaptive to the particular data arrangement present, and can potentially outperform the svs approaches. Still working with the SAEV representation, the simplest holistic approach is to treat each item in the smallest set as an eliminator, and search for it in each of the remaining sets. Conceptually, this method is identical to an interleaved version of svs. Other adaptive approaches have been proposed which primarily differ in the way that the eliminators are selected at each iteration. Barbay et al. [2006] provide a detailed overview of how such combinations interact, and summarize a range of previous work. The two prevailing eliminator selection techniques are the adaptive algorithm of Demaine et al. [2000], denoted adp for our purposes; and the sequential algorithm (seq) of Barbay and Kenyon [2002]. In adp, the sets are initially monotonically increasing in size. At each iteration, the eliminator is the next remaining item from the set with the fewest remaining elements. If a mismatch occurs before all q sets have been examined, the sets are reordered based on the number of unexamined items remaining in each set, and the successor from the smallest remaining subset becomes the new eliminator. This approach reduces the number of item-to-item comparisons expected to be required, but at the possibly non-trivial cost of reordering the q lists at each iteration of the main loop. Barbay and Kenyon [2002] proposed an alternative modification, and suggest that every list should be allowed to supply eliminators. Their sequential algorithm, denoted here as seq, uses as the next eliminator the element that caused the previous eliminator to be discarded, and continues the strict rotation among the sets from that point. Only when an eliminator value is found in all the sets and hence is part of the intersection s output is a new eliminator chosen from the smallest set. This approach has the advantage that the sets do not need to be reordered, while still allowing all of the sets to provide eliminators. However, this method suffers from a practical disadvantage: more F-SEARCH operations are likely to accrue when the eliminator is drawn from a populous set than when it is drawn from one of the sparse sets in the intersection. 3.2 Locality-Dependent, Adaptive Intersection Holistic methods may have a memory access pattern that is less localized than do svs methods, because all of the sets are processed concurrently. To ameliorate this risk, we propose a further alternative, described by Algorithm 4. The eliminator is initially drawn from the smallest set. When a mismatch occurs, the next eliminator is the larger of the mismatched value and the successor from the smallest set. Processing starts in S 2 if the eliminator is again taken from S 1, otherwise processing begins in S 1. The intuition behind this approach is two-fold. The first is that, while it is true that in the absence of other information, the best eliminator will arise in the smallest set, the likelihood of another set becoming significantly smaller than S 1 during processing is small. The second intuition is that, having discovered a bigger than anticipated jump in one of the sets, that value should naturally be tested against the first set, to see if additional items can be discarded.
8 8 J. Shane Culpepper and Alistair Moffat Algorithm 4 Max successor intersection, max INPUT: A list of q ordered sets S 1...S q. OUTPUT: An ordered set of answers A. 1: without loss of generality assume that S 1 S 2 S q 2: A { } 3: x FIRST(S 1 ) 4: startat 2 5: while x is defined do 6: for i = startat to q do 7: y F-SEARCH(S i, x) 8: if y > x then 9: x SUCC(S 1 ) 10: if y > x then 11: startat 1 12: x y 13: else 14: startat 2 15: end if 16: break 17: else if i = q then 18: APPEND(A, x) 19: x SUCC(S 1 ) 20: startat 2 21: end if 22: end for 23: end while 24: return A 3.3 Multi-Set Intersection in Practice In this section we empirically compare the intersection methods described in the previous sections, still working exclusively in the framework established by the SAEV representation. First, we describe the origins of the data used, and consider the statistical properties of two large query sets which form the basis of the empirical study. We then compare and contrast the various INTERSECT and F-SEARCH combinations, setting the scene for the introduction of other representations in the Sections 4 and 5. Our experiments are based on the integer lists that comprise the inverted index of the GOV2 collection of the TREC Terabyte Track, see The total collection contains just over 25 million crawled web documents, roughly 87 million distinct alphabetic words, and occupies 426 GB of space. The vocabulary and inverted lists were constructed using the Zettair search engine, see edu.au/zettair. Words that appeared with frequency one or two were assumed to be handled outside of the set of inverted lists, for example, within the vocabulary. After this reduction, a total of 19,783,975 index lists remained, each of which was then stored in SAEV format as an ordered sequence of document numbers in the range 1 to u = 25,205,181. Two query sets were used for the experiments. The first query set was extracted from a
9 Efficient set intersection for inverted indexing 9 Table I. The 27,004 Microsoft queries and 131,433 TREC queries. The average query length for the Microsoft and TREC queries is 2.73 and 4.00 terms respectively. The average n i columns show the average number of integers per index list across all terms for queries of that length. Query length Microsoft queries TREC queries Total Matches Average n i Total Matches Average n i q queries ( 000) ( 000) queries ( 000) ( 000) 2 15, ,018 28, , ,433 33, , , ,712 28, , , ,712 18, , ,169 10, , ,746 5, , ,050 2, , ,985 3, ,502 query log supplied by Microsoft, with the property that every query had a top-three result in the.gov domain at the time it was originally executed. The second query set was extracted from the 2005 and 2006 TREC million-query track. All single word queries from each set were eliminated, and the remaining queries filtered to ensure that each had at least one conjunctive match in the GOV2 collection. There were a total of 27,004 unique queries retained in the Microsoft query set, all of length two or greater; and 131,433 queries retained in the TREC query set. Table I shows the distribution of query lengths in the two test sequences; the average number of document matches for each query length; and the average number of documents containing each query term, computed for each query as ( q i=1 n i)/ q. Compared to the Microsoft queries of the same length, the TREC queries tend on average to involve terms that are less frequent in the collection, and thus more selective in terms of answer numbers. Across both logs, the longer queries tend to involve, on average, terms that are more frequent in the collection; but even relatively short queries of three words involved computing intersections over millions of document numbers. In order to focus solely on the efficiency of the intersection algorithms being tested, the inverted lists for the terms pertinent to each query were read into memory. The execution clock was started, and that query executed five consecutive times, in each case returning the full candidate set of document numbers. The clock was then stopped again, and the CPU time for the run was added to a running total, according to the length of the query evaluated. For example, the time recorded for queries of length two drawn from the Microsoft query set is the average of 5 15,517 = 77,585 query executions. Figure 1 compares the average CPU time per query for each intersection method. The top pair of graphs show the baseline approach of combining binary search with the different INTERSECT methods. The second row of graphs similarly shows the performance of the same methods when Golomb F-SEARCH is used; the third row, the performance of an exponential F-SEARCH; and the final pair of graphs the performance of an F-SEARCH based on interpolation search. In each of the four pairs of graphs, the left-hand one shows the measured behavior using the Microsoft query log, and the right-hand one shows the measured behavior using the TREC query log. Binary search (in the top pair of graphs) is relatively inefficient, as it generates more cache misses than the other methods. The result is a noticeable performance degradation relative to methods which achieve localized access. At the bottom of the figure, interpolation search performs significantly fewer comparisons on average across all INTERSECT methods (see Barbay et al. [2006]) and has a lower average case bound, but the added cost
10 10 J. Shane Culpepper and Alistair Moffat Time (msec) 100 Time (msec) 100 seq adp max bya svs Query length (words) Binary/Microsoft Query length (words) Binary/TREC Time (msec) 100 Time (msec) 100 seq adp max svs Query length (words) Golomb/Microsoft Query length (words) Golomb/TREC Time (msec) 100 Time (msec) 100 seq adp max svs Query length (words) Exponential/Microsoft Query length (words) Exponential/TREC Time (msec) 100 Time (msec) 100 seq adp max svs Query length (words) Interpolative/Microsoft Query length (words) Interpolative/TREC Fig. 1. Execution time required (in CPU milliseconds) of intersection algorithms as a function of query length, for two different query logs processed against the TREC GOV2 dataset, and assuming a SAEV set representation. All experiments were carried out on a 2.8 Ghz Intel Xeon with 2 GB of RAM. Note the logarithmic vertical scale.
11 Efficient set intersection for inverted indexing 11 Table II. Time required (in CPU milliseconds) for the svs intersection algorithms (which was the most efficient in all cases) as a function of query length and F-SEARCH algorithm, for two different query logs processed against the TREC GOV2 dataset, and assuming a SAEV set representation. All experiments were carried out on a 2.8 Ghz Intel Xeon with 2 GB of RAM. Query length Microsoft queries TREC queries q Bin Inter Exp Gol Bin Inter Exp Gol of the arithmetic involved in calculating each probe means that it is no faster that the other searching approaches. In terms of CPU performance, the svs and max methods outperform the adp and seq multi-set approaches, as a consequence of a more tightly localized memory access pattern. One issue that arose with the Golomb-based F-SEARCH approach depicted in the third row of graphs is the choice of parameter b. In the svs implementation, the value of b appropriate to each list is chosen immediately prior to that list being included in the ongoing sequence of intersections. But with the seq, adp, and max approaches, a value of b is computed for each list at the commencement of processing, based on the length of the shortest list. That same set of b values is then used throughout the computation, which means that if the intersection yields only a few answers, then the searching procedure may use b values that are too low. The best overall choices across the different eliminator selection approaches are the svs and max mechanisms, coupled with the exponential search or Golomb search for short queries, or coupled with the interpolative search for long ones. When conjunctive queries are computed using these combinations, the execution times of the svs and max methods tend not to grow as more terms are added to the query. This is because the cost is largely determined by the product of the frequency of the rarest element, and the number of terms. The longer the query, the more likely it is to include at least one low-frequency term, with the sum of the marginal savings that accrue on each one of the binary intersections more than recouping the cost of processing a greater number of lists. Finally, note that the top two graphs also show the binary search-based method of Baeza- Yates [2004], which is adaptive by virtue of the search sequence. It operates on two sets at a time, but within those two sets has little locality of reference when compared to the svs and max approaches, and is a little slower in practice. Table II shows the average time in milliseconds for each of the four F-SEARCH methods when combined with the svs approach, since it always the most efficient in practice. The exponential search (Exp) and Golomb search (Gol) exhibit nearly identical performance across all values of q, but with Exp having a slight edge throughout the range. This superiority could arise if the eventual answers to each query are not uniformly spread across the document range, and instead tend to form clusters within the document space. Interpolation search (Inter) is also fast when q is large, when the last intersections performed involve a very small set. Binary search (Bin) is never the fastest when combined with the svs intersection method. These observations also hold true when these F-SEARCH
12 12 J. Shane Culpepper and Alistair Moffat Table III. The average number of F-SEARCH calls initiated for the TREC query set. The average length of the shortest list, n 1, is also shown. Query length n 1 svs adp bya seq max 2 118, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,495 approaches are coupled with other algorithms, including seq and adp. Another way of quantifying efficiency is to count the number of F-SEARCH calls initiated. Table III shows the average number of F-SEARCH calls required across the 131,433 TREC queries, categorized by query length. The number of calls to resolve any given query is largely a function of the query length and the number of terms in the shortest list. However, as queries get longer, on average the rarest query term becomes progressively less frequent, and extended queries can involve fewer F-SEARCH calls than shorter ones, provided that an appropriate choice of eliminator is made at each step. In this regard, method seq is clearly more expensive than the others, and the new max method a little better. From these experiments we conclude that when the sets in question represent term occurrences in documents in a large collection of web pages, and are stored in SAEV representation, the classic small-versus-small approach to intersection is the fastest. In combination, the non-parameterized exponential F-SEARCH implementation is the approach that is the most versatile across the broad spectrum of query lengths. 4. COMPRESSED SET REPRESENTATIONS The intersection methods discussed so far assume each set is stored in SAEV format as a sorted array of explicit values. This is, however, an expensive way to store the sets that arise from the inverted lists in information retrieval systems, and any claims about relative performance must be re-evaluated when more compact storage representations are employed. 4.1 Compact Sequences of Relative Differences The index lists in a retrieval system are commonly stored as lists of first-order differences, or gaps, between consecutive items [Zobel and Moffat 2006]. Within this broad framework there are then many possible ways of representing the differences, and we will refer to these generically as being compact sequence of relative differences, or CSRD approaches, and take as axiomatic that the items in the sequence are unique integers and sorted, and thus that the differences are all strictly positive. For example, when converted to differences, the sorted set is transformed to S = {1, 4, 5, 6, 8, 12, 15, 16, 18, 20, 25, 26,27, 28, 30}, {1, 3, 1, 1, 2, 4, 3, 1, 2, 2,5, 1, 1, 1, 2}, which is then stored using some form of variable-length code that favors small values over large.
13 Efficient set intersection for inverted indexing 13 As a combinatorial limit, a set of n distinct items drawn from the universe 1...u can be represented in as few as ( ) u u! ( log 2 = log n (u n)!n! n log u ) n , (1) bits (see Brodnik and Munro [1999] or Sadakane and Grossi [2006] for discussion). Looking at this bound from the point of view of a sequence of n gaps d i 1 i n, any coding mechanism that represents the sequence in O(n log(u/n)) bits, where u = n i=1 d i, is a compact representation, and is at most a constant factor inefficient compared to the combinatorial lower bound. In particular, any static integer code with the property that the codeword for integer x requires O(log x) bits can be used. Codes that meet this requirement include the Elias γ and δ codes [Elias 1975]; and static byte-codes. Golomb codes are explicitly fitted to the situation described, and if all n-subsets of 1...u are equally likely, provide a one-parameter equivalent of the multi-parameter Huffman code that would be derived from the probability distribution governing the d-gaps. Witten et al. [1999] and Moffat and Turpin [2002] describe all of these methods, and we refer the reader to those descriptions rather than repeat them here. Unfortunately, the CSRD representations have a serious drawback: the differencing and compression transformations both produce representations that must necessarily be accessed sequentially. This restriction means that primitive set operations other than SUCC are expensive. In particular, the only viable F-SEARCH alternative is essentially a linear search, which means that INTERSECT of lists of length n 1 and n 2 requires O(n 1 + n 2 ) time. Even MEMBER queries incur an O(n) cost when using simple d-gap representations. That is, compact set representations are space effective, but unless they are enhanced with auxiliary structures, are not efficient for set intersection applications such as text retrieval. Recent work on succinct set representations which use sophisticated bitvector representations provide a viable alternative to balancing efficiency and effectiveness, but it is unclear how such data structures can be effectively integrated in current inverted index-based systems [Okanohara and Sadakane 2007; Claude and Navarro 2008]. 4.2 Bitvectors A set S of integer values over a known universe 1...u can also be represented using a bitvector, in an approach we refer to as BITV. A bitvector is a u-bit sequence in which the x th bit is 1 if and only if x S. For example, assuming that u = 32, the set S in Section 4.1 would be represented as the bitvector If the set being represented is dense over the universe 1...u, that is, u/n = O(1), then bitvectors are both space-effective and also access-efficient. On the other hand, when n u, bitvectors are more expensive than the compact representations described in the previous subsection. Using a bitvector dramatically shifts the cost balance of several of the primitive set operations. Operations INSERT, DELETE, and MEMBER all take O(1) time in the BITV representation; but UNION, DIFF, and INTERSECT take O(u) time, and without additional support via auxiliary structures, F-SEARCH, SUCC, and PRED also become more expensive. In practice, UNION, DIFF, and INTERSECT can benefit from bit-parallelism to obtain a constant factor speedup, but this does not affect the asymptotic cost of the operations. Control operations such as RANK and SELECT are also expensive in unadorned bitvector representations. If the application requires these or other control operations such as
14 14 J. Shane Culpepper and Alistair Moffat Table IV. Effectiveness of storage, and efficiency of access, for three different representations of integer sets, with emphasis on the operations needed in text retrieval systems, assuming that a subset of n (and a second larger one of size n 2, where the operation has two parameters) items in the range 1... u is being manipulated. In the F-SEARCH operation, d is the number of items that are stepped over. In the case of the BITV approach and the F-SEARCH operation it is assumed that the n elements form a random subset of 1... u. Attribute SAEV CSRD BITV Space required (bits) n log u n(log(u/n) ) u MEMBER (time) O(log n) O(n) O(1) F-SEARCH (time) O(log d) O(d) O(u/n) INTERSECT (time) O(n log(n 2 /n)) O(n + n 2 ) O(u) Table V. Total space cost (gigabytes) to store three different subsets of the inverted lists of terms appearing in more than two documents in the 426 GB TREC GOV2 collection. Data Representation TREC GOV2 Microsoft queries TREC queries 19,783,975 words 15,208 words 44,862 words BITV 58, SAEV, 32-bit integers CSRD, byte codes Combinatorial limit F-SEARCH, PRED, or SUCC, the basic bitvector representation is no longer sufficient. Jacobson [1989] showed that the addition of a controlled amount of extra space allows RANK and SELECT to be supported in O(log u) time. As a consequence, SUCC, and PRED can also be supported in equivalent time. Building on that work, Munro [1996] demonstrated that RANK and SELECT can be accomplished in O(1) time. The new structure, called an indexable bitvector, depends on the use of auxiliary lookup tables which store cumulative ranks for blocks of elements. The tradeoff for the performance boost is an additional o(u) bits of space, required to store the lookup tables. Additional variations on bitvectors have been reported recently, including some which attempt to reduce the space overhead associated with sparse bitvectors (see for example, Clark [1996], Pagh [2001], Raman et al. [2002], Okanohara and Sadakane [2007], and Claude and Navarro [2008]). However, the space overhead can still be significant in certain set arrangements. Note that the crucial motivation for many of the alternative bitvector arrangements is support for efficient RANK and SELECT operations, neither of which are strictly necessary for set intersection. Table IV summarizes the three alternative set representations that have been discussed. In each case it is assumed that a subset of n items in the range 1...u is being manipulated, and that the F-SEARCH operation steps past d members of the set. The column headed BITV further assumes that the set is dense. In the case of the CSRD and BITV representations, it is also assumed that no auxiliary information is being stored. (But note that in both cases F-SEARCH operations can be faster when the base arrangement is augmented by auxiliary index structures.) 4.3 Space Usage in Practice Table V shows the cost of storing three different subsets of the inverted lists of the GOV2 collection. In the second column, every term that appears in more than two of the collection s documents has its list included in the sum, and the values represent the cost of storing a full index. The third and fourth columns then show the cost of storing inverted lists for
15 Efficient set intersection for inverted indexing 15 only the subsets of the terms required by the two query sets indicated by the column heading. For example, storing the full set of inverted lists in SAEV format using 32-bit integers gives rise to an index of nearly 23 GB. When compared with the combinatorial cost of the full index (as defined in Equation 1, summed over all the lists) of 6 GB, the advantage of storing the index in CSRD format is apparent. Byte codes coupled with CSRD format do not attain the combinatorial bound, nevertheless they provide attractive space savings compared to uncompressed integers and SAEV format. At the other end of the spectrum, storing the full index in BITV format is prohibitively expensive; and even if only the required query terms are considered, the BITV format which is the most efficient in terms of MEMBER queries is relatively costly, even if those terms could somehow have been known in advance. 5. BALANCING SPACE AND TIME USAGE For CSRD representations it is possible to accelerate F-SEARCH operations by adding additional information to the compressed sequence. For example, Moffat and Zobel [1996] add a synchronization point every n th position, so that blocks of n items can be bypassed when MEMBER and F-SEARCH operations involve search keys not present in that block. More elaborate approaches have also been proposed which attempt to offset the costs of a linear scan through all d-gaps using variations on balanced binary search trees. Gupta et al. [2006] describe a two-level data structure where each level is itself searchable and compressed, extending earlier work by Blandford and Blelloch [2004]. In the Gupta et al. [2006] method, each block of elements at the lower level is represented as a balanced binary search tree, and stored implicitly via a pre-order traversal, with additional skip pointers embedded to find each child s left subtree. Sitting on top of each tree block is an index which allows the correct tree to be quickly identified. By balancing the size and efficiency of the two structures, good asymptotic performance is achieved. 5.1 Auxiliary Indexing In this section we propose a more pragmatic approach to address the same need. The structure, which we refer to as an auxiliary index, balances space and time usage in a relatively straightforward manner, and allows fast implementation. It makes use of a partial index of uncompressed items together with offsets into the compressed sequence. Figure 2 outlines the proposed arrangement. First, every p th element is extracted from the compressed list, added to an auxiliary array, and stored as an uncompressed integer. The choice of a value for p is discussed shortly. Next, the remaining items are represented as d-gaps, and stored as groups of p 1 differences, compressed sequentially. Finally, a bit offset (or byte offset, in the case of byte-code compression techniques) is added to the auxiliary array, so that the blocks of the compressed data can be accessed independently of each other. When a MEMBER operation is required, the keys in the auxiliary array are traversed using any SAEV-based searching method, including the F-SEARCH approaches described in Section 2. If the value being sought is located in the auxiliary array, it is returned. If not, a sequential search is undertaken in the appropriate block of p elements using a CSRD mechanism. Alternatively, the block can be completely decompressed into an array, and searched using a SAEV-based MEMBER operation. The cost of searching when the set contains n values is at most O(log(n/p)) for a binary search in the auxiliary index, followed by O(p)-time spent decoding and searching within
16 16 J. Shane Culpepper and Alistair Moffat (a) log n log n log n log n (b) (c) Fig. 2. Auxiliary indexing. In this example p = 4, so every fourth element from the original list (part(a), shaded entries) is extracted and stored in the auxiliary array (part (b)), together with a byte offset to the block of p 1 remaining elements. The block elements are then encoded as d-gaps and compressed (part (c)). the block. If p = k log n, for some constant k, the combined search cost for the two phases is O(log n). In terms of space, and assuming an efficient code, the cost of storing each difference is log(u/n) bits in an amortized sense. There are (p 1) items in each p item block stored in this way, or (p 1)n/p items in total. The other n/p elements are stored in the auxiliary array, and require log u bits for each stored element, plus log(n log(u/n)) log n+log log u bits for the access pointer. Over both components the cost is bounded by p 1 ( p n log u ) n n (log u + log n + log log u) p bits, which is readily reformulated as n (log u ) n n (2 logn + log log u 1.44). p Then, when p = k log n, this simplifies to n (log u ) n n ( log log u 2 + k log n 1.44 ), log n which is less than n (log u ) n n ( 2 + k ) log log u. log n That is, for an additional O(n/k) bits compared to Equation 1, the search time in the compact representation reduces to O(k log n), provided that n log u. In real terms, if k = 1 and u 2 64, the additional cost of the auxiliary index is less than 3 bits per pointer when n 64, and less than 2.5 bits per pointer when n 4096.
17 Efficient set intersection for inverted indexing 17 Table VI. Total space cost (gigabytes) of CSRD representation and auxiliary indexing, on the same basis as is presented in Table V. Data Representation TREC GOV2 Microsoft queries TREC queries 19,783,975 words 15,208 words 44,862 words CSRD, byte codes CSRD, byte codes, auxiliary index, k = CSRD, byte codes, auxiliary index, k = CSRD, byte codes, auxiliary index, k = Time (msec) 100 Time (msec) 100 svs+bc svs+bc+aux bvc svs Query length (words) Microsoft Queries Query length (words) TREC queries Fig. 3. Performance of set intersection algorithms for different query lengths against the TREC GOV2 dataset, measured using a 2.8 Ghz Intel Xeon with 2 GB of RAM. In each of the two graphs two CSRD-based methods are shown: svs+bc, the sequential processing of byte-codes; and svs+bc+aux, byte-codes indexed by an auxiliary array with k = 2. Each graph also includes one SAEV-based method, svs, a small-versus-small approach using exponential search; and use of a pure bitvector approach, bvc. The vertical scale is the same as was used in Figure 1, and the results here can be directly compared against the two columns of graphs in Figure 1. A potential disadvantage of the new approach is that F-SEARCH operations over a distance of d are no longer guaranteed to take O(log d) time. In the worst case, sequential decoding of a block of d-gaps can lead to O(log n) time instead. However, this is generally not a significant problem, as the block-based approach is well suited to blockwise hierarchical memory models. When compared with the inline approach described by Moffat and Zobel [1996], our blocks are smaller on average, and the skip pointers are maintained separately from the compressed d-gap sequence. The revised approach allows faster F-SEARCH operations, and thus faster INTERSECT computations, but at the cost of a small amount of additional space. In recent independent work Sanders and Transier [2007] also investigate two-level representations to improve intersection in compact sets. The key difference between their work and ours is that they use a randomization technique to ensure that each bucket on average has around log n items, and get the benefit of a simpler auxiliary structure that can be implemented as a look-up table, whereas we count an exact number of elements into each bucket, and hence need to search within the auxiliary table to identify the correct block. 5.2 Auxiliary Indexes in Practice Table VI shows the total space usage to store the full GOV2 index and two index subsets used in the experiments in CSRD format, without the auxiliary index (this row is repeated from Table V), and with an auxiliary index, using three different values of k. The augmented indexes all use more space than the fully byte-coded list, as expected, but even with k = 1 the additional cost is relatively modest. Figure 3 compares the SAEV binary representation and the alternative CSRD representa-
18 18 J. Shane Culpepper and Alistair Moffat tion. Fully compressed representations such as the svs+bc approach perform well for short queries, but are much slower than the SAEV-based svs approach on longer ones, in which it is more likely that at least some common terms will arise. Use of the auxiliary array in the svs+bc+aux method increases processing speed on long queries, and allows intersections to be handled in times closer to those attained by the uncompressed svs approach. This improvement is a result of intersection benefiting from non-sequential access and, as queries get longer, the increasing sparsity of the most discriminating term list. Figure 3 also shows the time taken by the bitvector approach, bvc, which is usefully fast on short queries, but as expected, has a cost that grows approximately linearly in the number of query terms. Bitvectors are able to store common query terms in relatively small amounts of space. Indeed, their only real deficiency is the exorbitant storage costs for rare terms, an observation that leads directly to the hybrid approach that is explored in the next section. 5.3 Hybrid Representations The simplicity of bitvectors, and their useful blend of efficiency and effectiveness for INTERSECT and MEMBER queries on dense sets, suggests that using them to store at least some of the term lists of the index may be beneficial. To this end, we now consider a hybrid approach, in which the dense lists in the index, corresponding to frequently occurring terms, are stored using a BITV representation, and the sparse terms are stored using a CSRD representation. Given that each byte-coded difference occupies a minimum of eight bits, using a bitvector for all terms that occur in more than u/8 of the documents in a collection containing a total of u documents cannot increase the index size. Other thresholds are also possible, and in the experiments described shortly, the bitvector representation is used whenever more than u/k of the documents contain that term, for values of k in the set {8, 16, 32}. Two alternative ways of using the resultant hybrid index have been evaluated. In the first method, denoted hyb+m1, the sets of byte coded and bitvector lists are intersected separately, and then combined using a sequence of O(1)-time MEMBER operations. That is, if there are any BITV terms, they are intersected using bitwise AND operations to yield a bitvector B. If there are no byte-coded CSRD sets, then the expanded set of document numbers derived from B is returned. Or, if there are byte-coded sets, they are intersected using the svs approach to yield a candidate set C. Then, if there are no bitvector sets, C is returned. Otherwise, for each x C, if B[x] = 1, then x is appended to the answer set. In the second hybrid method, hyb+m2, all byte-coded lists are intersected to produce a candidate list. Then, each of the remaining bitvector lists is searched via a MEMBER query, replacing the bitvector INTERSECT operations with multiple MEMBER operations, each of which takes O(1) time. The motivation for this alternative comes from the realization that intersection of the byte-coded sets should result in a sparse set of potential candidates, and that a sequence of MEMBER queries may be preferable to any O(u)-time INTERSECT operations. Algorithm 5 describes this second approach in detail. 5.4 Hybrid Representations in Practice Table VII shows the cost of storing the GOV2 index data using compressed lists and bitvectors in a hybrid approach. The most effective partitioning point for the compact hybrid representation is k = 8, with terms occurring in fewer than u/8 = 3,150,648 documents stored using a CSRD approach and the byte-code representation. Note that when k = 8
19 Efficient set intersection for inverted indexing 19 Algorithm 5 Hybrid intersection method two, hyb+m2 INPUT: A list of CSRD-representation byte coded term lists CSRD 1... CSRD x, and a list of BITV-representation term lists, BITV 1... BITV y, where x + y = q. OUTPUT: An ordered set of answers, as 32-bit integers. 1: A { } 2: if x = 0 then 3: B BITV 1 4: for i 2 to y do 5: B B bit-and BITV i 6: end for 7: return DECODE-BITV(B) 8: end if 9: C DECODE-CSRD(CSRD 1 ) 10: for i 2 to x do 11: C INTERSECT(C, DECODE-CSRD(CSRD i )) 12: end for 13: for i 1 to y do 14: for each d C do 15: if NOT MEMBER(BITV i, d) then 16: DELETE(C, d) 17: end if 18: end for 19: end for 20: return C Table VII. Total space cost (gigabytes) of hybrid BITV/CSRD representations, on the same basis as is presented in Table V and Table VI. Data Representation TREC GOV2 Microsoft queries TREC queries 19,783,975 words 15,208 words 44,862 words Hybrid bitvector and byte code, k = Hybrid bitvector and byte code, k = Hybrid bitvector and byte code, k = there is a net saving compared to the fully byte-coded index (Table V), because even in the dense term lists, there are some d-gaps that require more than one byte to code. Even with k = 16 the overall index is smaller than the byte-coded one, and the same relationship holds for the subsets of the term lists that appear in the two experimental query streams. Table VIII shows the fraction of the GOV2 collection s index lists that are handled as bitvectors, for three different threshold values k. As a fraction of the vocabulary of the collection, the terms that are sufficiently frequent to warrant bitvector index lists are a tiny minority, even when k = 32. But when the two query logs are evaluated, a much greater fraction of bitvector terms arises, because queries tend not to use the rare terms. The top pane of Figure 4 lists the 188 most frequent terms in the GOV2 collection, each of which appears in more than one eighth of the web documents in the collection, so is stored as a bitvector in the hybrid BITV/CSRD method when k 8. The bottom pane then shows a sequence of ten consecutive queries extracted from the TREC query log, with each of
20 20 J. Shane Culpepper and Alistair Moffat Table VIII. Fraction of index lists stored and processed as bitvectors for three different threshold values k, and two different query streams. Just 188 index lists are stored in BITV format when k = 8 (listed in Figure 4); even so, one or more of those terms appears in 35% of the Microsoft queries, and in 50% of the TREC queries. Attribute Hybrid parameter k = 8 k = 16 k = 32 Fraction of index lists stored in BITV format 0.001% 0.003% 0.007% Fraction of Microsoft queries with one BITV index list 24.6% 31.0% 34.6% Fraction of Microsoft queries with multiple BITV index lists 10.7% 21.0% 33.5% Fraction of TREC queries with one BITV index list 28.6% 29.2% 26.8% Fraction of TREC queries with multiple BITV index lists 21.9% 33.7% 47.9% of to the and for a in on by this is information with home from at or are as not all 1 be us other state search last contact new an page 2 that about national data public may have site if 3 department use you no 2003 available more 4 5 services has privacy center which resources your will it 10 name service number was system help date library can please only also 7 office research 6 one been i these 8 program health related its 12 management through see but links 30 federal states s do report development any index washington support following who year than type 25 when general programs subject first description using where administration out used 2002 their comments modified 11 policy 23 web 9 questions there time 19 government updated security each map title 16 order make back code find part united law within such accessibility current 14 advanced does 13 both two our how areas years over d they local were c 22 next county includes include 31 disclaimer under agency area into based click need weather in 8 london how 8 to 8 find 8 out 8 your 8 body 32 mas index 8 red 32 dead revolver cheats grand theft auto san 32 andreas cheat codes vacuum tube pins heaven dj sammy and 8 yanou wings of 8 desire escort ny vegetable disease 32 control 16 sprays pinnacle village bike rentals on 8 the 8 carolina islands Fig. 4. The 188 most frequent words in the GOV2 collection, in decreasing order of the number of documents containing them, each of which appears in more than one eighth of the approximately 25 million web documents (top pane); plus a sequence of ten queries extracted from the TREC query set, annotated to show which words are represented as bitvectors for the three different values of k that were tested. the common terms annotated to show the value of k (of 8, 16, and 32) at which that term toggles from CSRD format to BITV format in the hybrid arrangement. For example, the query term control is stored in CSRD format using byte-codes when k = 8, but is stored as a bitvector when k = 16 and k = 32. Table IX shows the average cost of processing the set intersections arising from the TREC query stream using the hyb+m1 and hyb+m2 methods, broken down by query length, and with techniques built on the SAEV, CSRD, and BITV representations also included. Three different threshold points k = {8, 16, 32} are shown. The svs approach, using a SAEV data representation, is efficient at all query lengths, and provides a competitive benchmark. Even with the auxiliary index, the CSRD data representation is not competitive in terms of query speed, and nor is the pure BITV representation. In the latter case, long queries are especially expensive, because of the large amount of index data that must be processed via binary AND operations. The hyb+m2 mechanism shown in Algorithm 5 is markedly superior to the hyb+m1 approach, with the difference between the two being the elimination of the binary AND operations. Even when the index size is minimized at k = 8, queries are resolved in times similar to the svs+bc+aux approach; and when a larger index is permitted using k = 32,
Binary Codes for Nonuniform
Binary Codes for Nonuniform Sources (dcc-2005) Alistair Moffat and Vo Ngoc Anh Presented by:- Palak Mehta 11-20-2006 Basic Concept: In many applications of compression, decoding speed is at least as importantMore information
Storage Management for Files of Dynamic Records
Storage Management for Files of Dynamic Records Justin Zobel Department of Computer Science, RMIT, GPO Box 2476V, Melbourne 3001, Australia. email@example.com Alistair Moffat Department of Computer ScienceMore information
Inverted Indexes Compressed Inverted Indexes. Indexing and Searching, Modern Information Retrieval, Addison Wesley, 2010 p. 40
Inverted Indexes Compressed Inverted Indexes Indexing and Searching, Modern Information Retrieval, Addison Wesley, 2010 p. 40 Compressed Inverted Indexes It is possible to combine index compression andMore information
Compressing the Digital Library
Compressing the Digital Library Timothy C. Bell 1, Alistair Moffat 2, and Ian H. Witten 3 1 Department of Computer Science, University of Canterbury, New Zealand, email@example.com 2 DepartmentMore information
Information Retrieval
Information Retrieval Indexes All slides unless specifically mentioned are Addison Wesley, 2008; Anton Leuski & Donald Metzler 2012 1 Search Process Information need query text objects representation representationMore information
An Evaluation of Self-adjusting Binary Search Tree Techniques
SOFTWARE PRACTICE AND EXPERIENCE, VOL. 23(4), 369 382 (APRIL 1993) An Evaluation of Self-adjusting Binary Search Tree Techniques jim bell and gopal gupta Department of Computer Science, James Cook University,More information
Information Retrieval
Information Retrieval ETH Zürich, Fall 2012 Thomas Hofmann LECTURE 4 INDEX COMPRESSION 10.10.2012 Information Retrieval, ETHZ 2012 1 Overview 1. Dictionary Compression 2. Zipf s Law 3. Posting List CompressionMore information
Experimental Comparison of Set Intersection Algorithms for Inverted Indexing
ITAT 213 Proceedings, CEUR Workshop Proceedings Vol. 13, pp. 58 64 http://ceur-ws.org/vol-13, Series ISSN 1613-73, c 213 V. Boža Experimental Comparison of Set Intersection Algorithms for Inverted IndexingMore information
A Catalogue of the Steiner Triple Systems of Order 19
A Catalogue of the Steiner Triple Systems of Order 19 Petteri Kaski 1, Patric R. J. Östergård 2, Olli Pottonen 2, and Lasse Kiviluoto 3 1 Helsinki Institute for Information Technology HIIT University ofMore information
Multimedia Communications. Huffman Coding
Multimedia Communications Huffman Coding Optimal codes Suppose that a i -> w i C + is an encoding scheme for a source alphabet A={a 1,, a N }. Suppose that the source letter a 1,, a N occur with relativeMore information
ABSTRACT EFFICIENT EXTERNAL SORTING ON FLASH MEMORY EMBEDDED DEVICES Tyler Cossentine and Ramon Lawrence Department of Computer Science, University of British Columbia Okanagan Kelowna, BC, Canada email@example.com information
Why? A central concept in Computer Science. Algorithms are ubiquitous.
Analysis of Algorithms: A Brief Introduction Why? A central concept in Computer Science. Algorithms are ubiquitous. Using the Internet (sending email, transferring files, use of search engines, onlineMore information
Techniques Covered in this Class. Inverted List Compression Techniques. Recap: Search Engine Query Processing. Recap: Search Engine Query Processing
Recap: Search Engine Query Processing Basically, to process a query we need to traverse the inverted lists of the query terms Lists are very long and are stored on disks Challenge: traverse lists as quicklyMore information
Physical Data Organization
Physical Data Organization Database design using logical model of the database - appropriate level for users to focus on - user independence from implementation details Performance - other major factorMore information
Inverted Files for Text Search Engines
Table of Contents Inverted Files for Text Search Engines...2 JUSTIN ZOBEL And ALISTAIR MOFFAT...2 by M. Levent KOC...2 Sample Collection for examples:...2 Collection with only case-folding...2 CollectionMore information
Image Compression through DCT and Huffman Coding Technique
International Journal of Current Engineering and Technology E-ISSN 2277 4106, P-ISSN 2347 5161 2015 INPRESSCO, All Rights Reserved Available at http://inpressco.com/category/ijcet Research Article RahulMore information
Fast Sequential Summation Algorithms Using Augmented Data Structures
Fast Sequential Summation Algorithms Using Augmented Data Structures Vadim Stadnik firstname.lastname@example.com Abstract This paper provides an introduction to the design of augmented data structures that offerMore information
Information, Entropy, and Coding
Chapter 8 Information, Entropy, and Coding 8. The Need for Data Compression To motivate the material in this chapter, we first consider various data sources and some estimates for the amount of data associatedMore information
Data Warehousing und Data Mining
Data Warehousing und Data Mining Multidimensionale Indexstrukturen Ulf Leser Wissensmanagement in der Bioinformatik Content of this Lecture Multidimensional Indexing Grid-Files Kd-trees Ulf Leser: DataMore information
Big Data Technology Map-Reduce Motivation: Indexing in Search Engines
Big Data Technology Map-Reduce Motivation: Indexing in Search Engines Edward Bortnikov & Ronny Lempel Yahoo Labs, Haifa Indexing in Search Engines Information Retrieval s two main stages: Indexing processMore information
Analysis of Compression Algorithms for Program Data
Analysis of Compression Algorithms for Program Data Matthew Simpson, Clemson University with Dr. Rajeev Barua and Surupa Biswas, University of Maryland 12 August 3 Abstract Insufficient available memoryMore information
Improved Single and Multiple Approximate String Matching
Improved Single and Multiple Approximate String Matching Kimmo Fredriksson Department of Computer Science, University of Joensuu, Finland Gonzalo Navarro Department of Computer Science, University of ChileMore information
Self-Indexing Inverted Files for Fast Text Retrieval
Self-Indexing Inverted Files for Fast Text Retrieval Alistair Moffat Justin Zobel February 1994 Abstract Query processing costs on large text databases are dominated by the need to retrieve and scan theMore information
! Overview! Measures of Query Cost! Selection Operation! Sorting! Join Operation! Other Operations! Evaluation of Expressions
Chapter 13: Query Processing Chapter 13: Query Processing! Overview! Measures of Query Cost! Selection Operation! Sorting! Join Operation! Other Operations! Evaluation of Expressions Basic Steps in QueryMore information
A COOL AND PRACTICAL ALTERNATIVE TO TRADITIONAL HASH TABLES ULFAR ERLINGSSON, MARK MANASSE, FRANK MCSHERRY MICROSOFT RESEARCH SILICON VALLEY MOUNTAIN VIEW, CALIFORNIA, USA ABSTRACT Recent advances in theMore information
character E T A S R I O D frequency
Data Compression Data compression is any process by which a digital (e.g. electronic) file may be transformed to another ( compressed ) file, such that the original file may be fully recovered from theMore information
INTRODUCTION The collection of data that makes up a computerized database must be stored physically on some computer storage medium.
Chapter 4: Record Storage and Primary File Organization 1 Record Storage and Primary File Organization INTRODUCTION The collection of data that makes up a computerized database must be stored physicallyMore information
MapReduce and Distributed Data Analysis. Sergei Vassilvitskii Google Research
MapReduce and Distributed Data Analysis Google Research 1 Dealing With Massive Data 2 2 Dealing With Massive Data Polynomial Memory Sublinear RAM Sketches External Memory Property Testing 3 3 Dealing WithMore information
Data storage Tree indexes
Data storage Tree indexes Rasmus Pagh February 7 lecture 1 Access paths For many database queries and updates, only a small fraction of the data needs to be accessed. Extreme examples are looking or updatingMore information
Can you design an algorithm that searches for the maximum value in the list?
The Science of Computing I Lesson 2: Searching and Sorting Living with Cyber Pillar: Algorithms Searching One of the most common tasks that is undertaken in Computer Science is the task of searching. WeMore information
In-Memory Databases Algorithms and Data Structures on Modern Hardware. Martin Faust David Schwalb Jens Krüger Jürgen Müller
In-Memory Databases Algorithms and Data Structures on Modern Hardware Martin Faust David Schwalb Jens Krüger Jürgen Müller The Free Lunch Is Over 2 Number of transistors per CPU increases Clock frequencyMore information
Compression for IR. Lecture 5. Lecture 5 Information Retrieval 1
Compression for IR Lecture 5 Lecture 5 Information Retrieval 1 IR System Layout Lexicon (w, *occ) Occurrences (d, f t,d ) Locations (d, *pos) Documents 2 Why Use Compression? More storage inverted fileMore information
Efficient Processing of Joins on Set-valued Attributes
Efficient Processing of Joins on Set-valued Attributes Nikos Mamoulis Department of Computer Science and Information Systems University of Hong Kong Pokfulam Road Hong Kong firstname.lastname@example.com Abstract Object-orientedMore information
Chapter 13: Query Processing. Basic Steps in Query Processing
Chapter 13: Query Processing! Overview! Measures of Query Cost! Selection Operation! Sorting! Join Operation! Other Operations! Evaluation of Expressions 13.1 Basic Steps in Query Processing 1. ParsingMore information
Algorithms. Theresa Migler-VonDollen CMPS 5P
Algorithms Theresa Migler-VonDollen CMPS 5P 1 / 32 Algorithms Write a Python function that accepts a list of numbers and a number, x. If x is in the list, the function returns the position in the listMore information
86 CHAPTE A MEMOY EFFICIENT SPEECH CODING SCHEME WITH FAST DECODING. INTODUCTION Huffman coding proposed by Huffman (9) is the most widely used minimal prefix coding algorithm because of its robustness,More information
2 Exercises and Solutions
2 Exercises and Solutions Most of the exercises below have solutions but you should try first to solve them. Each subsection with solutions is after the corresponding subsection with exercises. 2.1 SortingMore information
Query Processing, optimization, and indexing techniques
Query Processing, optimization, and indexing techniques What s s this tutorial about? From here: SELECT C.name AS Course, count(s.students) AS Cnt FROM courses C, subscription S WHERE C.lecturer = CaldersMore information
Record Storage and Primary File Organization
Record Storage and Primary File Organization 1 C H A P T E R 4 Contents Introduction Secondary Storage Devices Buffering of Blocks Placing File Records on Disk Operations on Files Files of Unordered RecordsMore information
Universal hashing. In other words, the probability of a collision for two different keys x and y given a hash function randomly chosen from H is 1/m.
Universal hashing No matter how we choose our hash function, it is always possible to devise a set of keys that will hash to the same slot, making the hash scheme perform poorly. To circumvent this, weMore information
So today we shall continue our discussion on the search engines and web crawlers. (Refer Slide Time: 01:02)
Internet Technology Prof. Indranil Sengupta Department of Computer Science and Engineering Indian Institute of Technology, Kharagpur Lecture No #39 Search Engines and Web Crawler :: Part 2 So today weMore information
LZ77. Example 2.10: Let T = badadadabaab and assume d max and l max are large. phrase b a d adadab aa b
LZ77 The original LZ77 algorithm works as follows: A phrase T j starting at a position i is encoded as a triple of the form distance, length, symbol. A triple d, l, s means that: T j = T [i...i + l] =More information
Almost every lossy compression system contains a lossless compression system
Lossless compression in lossy compression systems Almost every lossy compression system contains a lossless compression system Lossy compression system Transform Quantizer Lossless Encoder Lossless DecoderMore information
Wayne State University ECE 7650: Scalable and Secure Internet Services and Architecture SMALL INDEX LARGE INDEX (SILT) A Memory Efficient High Performance Key Value Store QA REPORT Instructor: Dr. SongMore information
FAWN - a Fast Array of Wimpy Nodes
University of Warsaw January 12, 2011 Outline Introduction 1 Introduction 2 3 4 5 Key issues Introduction Growing CPU vs. I/O gap Contemporary systems must serve millions of users Electricity consumedMore information
MapReduce With Columnar Storage
SEMINAR: COLUMNAR DATABASES 1 MapReduce With Columnar Storage Peitsa Lähteenmäki Abstract The MapReduce programming paradigm has achieved more popularity over the last few years as an option to distributedMore information
Chapter 2 Data Storage
Chapter 2 22 CHAPTER 2. DATA STORAGE 2.1. THE MEMORY HIERARCHY 23 26 CHAPTER 2. DATA STORAGE main memory, yet is essentially random-access, with relatively small differences Figure 2.4: A typicalMore information
Resource Allocation Schemes for Gang Scheduling
Resource Allocation Schemes for Gang Scheduling B. B. Zhou School of Computing and Mathematics Deakin University Geelong, VIC 327, Australia D. Walsh R. P. Brent Department of Computer Science AustralianMore information
Key Components of WAN Optimization Controller Functionality
Key Components of WAN Optimization Controller Functionality Introduction and Goals One of the key challenges facing IT organizations relative to application and service delivery is ensuring that the applicationsMore information
Succinct Data Structures for Data Mining
Succinct Data Structures for Data Mining Rajeev Raman University of Leicester ALSIP 2014, Tainan Overview Introduction Compressed Data Structuring Data Structures Applications Libraries End Big Data vs.More information
Binary search tree with SIMD bandwidth optimization using SSE
Binary search tree with SIMD bandwidth optimization using SSE Bowen Zhang, Xinwei Li 1.ABSTRACT In-memory tree structured index search is a fundamental database operation. Modern processors provide tremendousMore information
MS SQL Performance (Tuning) Best Practices:
MS SQL Performance (Tuning) Best Practices: 1. Don t share the SQL server hardware with other services If other workloads are running on the same server where SQL Server is running, memory and other hardwareMore information
Benchmarking Hadoop & HBase on Violin
Technical White Paper Report Technical Report Benchmarking Hadoop & HBase on Violin Harnessing Big Data Analytics at the Speed of Memory Version 1.0 Abstract The purpose of benchmarking is to show advantagesMore information
The Union-Find Problem Kruskal s algorithm for finding an MST presented us with a problem in data-structure design. As we looked at each edge,
The Union-Find Problem Kruskal s algorithm for finding an MST presented us with a problem in data-structure design. As we looked at each edge, cheapest first, we had to determine whether its two endpointsMore information
Chapter 13 File and Database Systems
Chapter 13 File and Database Systems Outline 13.1 Introduction 13.2 Data Hierarchy 13.3 Files 13.4 File Systems 13.4.1 Directories 13.4. Metadata 13.4. Mounting 13.5 File Organization 13.6 File AllocationMore information
Chapter 13 File and Database Systems
Chapter 13 File and Database Systems Outline 13.1 Introduction 13.2 Data Hierarchy 13.3 Files 13.4 File Systems 13.4.1 Directories 13.4. Metadata 13.4. Mounting 13.5 File Organization 13.6 File AllocationMore information
Persistent Binary Search Trees
Persistent Binary Search Trees Datastructures, UvA. May 30, 2008 0440949, Andreas van Cranenburgh Abstract A persistent binary tree allows access to all previous versions of the tree. This paper presentsMore information
Rethinking SIMD Vectorization for In-Memory Databases
SIGMOD 215, Melbourne, Victoria, Australia Rethinking SIMD Vectorization for In-Memory Databases Orestis Polychroniou Columbia University Arun Raghavan Oracle Labs Kenneth A. Ross Columbia University LatestMore information
A Survey on Efficient Hashing Techniques in Software Configuration Management
A Survey on Efficient Hashing Techniques in Software Configuration Management Bernhard Grill Vienna University of Technology Vienna, Austria Email: firstname.lastname@example.com Abstract This paper presentsMore information
Fast Arithmetic Coding (FastAC) Implementations
Fast Arithmetic Coding (FastAC) Implementations Amir Said 1 Introduction This document describes our fast implementations of arithmetic coding, which achieve optimal compression and higher throughput byMore information
Fast Phrase Querying with Combined Indexes
Fast Phrase Querying with Combined Indexes HUGH E. WILLIAMS, JUSTIN ZOBEL, and DIRK BAHLE RMIT University Search engines need to evaluate queries extremely fast, a challenging task given the quantitiesMore information
Parallel Scalable Algorithms- Performance Parameters
www.bsc.es Parallel Scalable Algorithms- Performance Parameters Vassil Alexandrov, ICREA - Barcelona Supercomputing Center, Spain Overview Sources of Overhead in Parallel Programs Performance Metrics forMore information
Efficiency of algorithms. Algorithms. Efficiency of algorithms. Binary search and linear search. Best, worst and average case.
Algorithms Efficiency of algorithms Computational resources: time and space Best, worst and average case performance How to compare algorithms: machine-independent measure of efficiency Growth rate ComplexityMore information
Lecture 2 February 12, 2003
6.897: Advanced Data Structures Spring 003 Prof. Erik Demaine Lecture February, 003 Scribe: Jeff Lindy Overview In the last lecture we considered the successor problem for a bounded universe of size u.More information
ABSTRACT 1. INTRODUCTION. Kamil Bajda-Pawlikowski email@example.com
Kamil Bajda-Pawlikowski email@example.com Querying RDF data stored in DBMS: SPARQL to SQL Conversion Yale University technical report #1409 ABSTRACT This paper discusses the design and implementationMore information
Volume 2, No. 3, March 2011 Journal of Global Research in Computer Science RESEARCH PAPER Available Online at www.jgrcs.info IMPROVING PERFORMANCE OF RANDOMIZED SIGNATURE SORT USING HASHING AND BITWISEMore information
PART IV Performance oriented design, Performance testing, Performance tuning & Performance solutions. Outline. Performance oriented design
PART IV Performance oriented design, Performance testing, Performance tuning & Performance solutions Slide 1 Outline Principles for performance oriented design Performance testing Performance tuning GeneralMore information
Benchmarking Cassandra on Violin
Technical White Paper Report Technical Report Benchmarking Cassandra on Violin Accelerating Cassandra Performance and Reducing Read Latency With Violin Memory Flash-based Storage Arrays Version 1.0 AbstractMore information
Index Compression using Fixed Binary Codewords
Index Compression using Fixed Binary Codewords Vo Ngoc Anh Alistair Moffat Department of Computer Science and Software Engineering The University of Melbourne Victoria 3010, Australia http://www.cs.mu.oz.au/More information
Jan F. Prins. Work-efficient Techniques for the Parallel Execution of Sparse Grid-based Computations TR91-042
Work-efficient Techniques for the Parallel Execution of Sparse Grid-based Computations TR91-042 Jan F. Prins The University of North Carolina at Chapel Hill Department of Computer Science CB#3175, SittersonMore information
Lecture Notes on Spanning Trees
Lecture Notes on Spanning Trees 15-122: Principles of Imperative Computation Frank Pfenning Lecture 26 April 26, 2011 1 Introduction In this lecture we introduce graphs. Graphs provide a uniform modelMore information
ProTrack: A Simple Provenance-tracking Filesystem
ProTrack: A Simple Provenance-tracking Filesystem Somak Das Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology firstname.lastname@example.com Abstract Provenance describes a fileMore information
Chapter 6: Episode discovery process
Chapter 6: Episode discovery process Algorithmic Methods of Data Mining, Fall 2005, Chapter 6: Episode discovery process 1 6. Episode discovery process The knowledge discovery process KDD process of analyzingMore information
CS 2112 Spring 2014. 0 Instructions. Assignment 3 Data Structures and Web Filtering. 0.1 Grading. 0.2 Partners. 0.3 Restrictions
CS 2112 Spring 2014 Assignment 3 Data Structures and Web Filtering Due: March 4, 2014 11:59 PM Implementing spam blacklists and web filters requires matching candidate domain names and URLs very rapidlyMore information
12 Abstract Data Types
12 Abstract Data Types 12.1 Source: Foundations of Computer Science Cengage Learning Objectives After studying this chapter, the student should be able to: Define the concept of an abstract data type (ADT).More information
MODULE 15 Clustering Large Datasets LESSON 34
MODULE 15 Clustering Large Datasets LESSON 34 Incremental Clustering Keywords: Single Database Scan, Leader, BIRCH, Tree 1 Clustering Large Datasets Pattern matrix It is convenient to view the input dataMore information
CHAPTER 8 PIPELINING CHAPTER OBJECTIVES In this chapter you will learn about: Pipelining as a means for executing machine instructions concurrently Various hazards that cause performance degradation inMore information
Creating Synthetic Temporal Document Collections for Web Archive Benchmarking
Creating Synthetic Temporal Document Collections for Web Archive Benchmarking Kjetil Nørvåg and Albert Overskeid Nybø Norwegian University of Science and Technology 7491 Trondheim, Norway Abstract. InMore information
FPGA-based Multithreading for In-Memory Hash Joins
FPGA-based Multithreading for In-Memory Hash Joins Robert J. Halstead, Ildar Absalyamov, Walid A. Najjar, Vassilis J. Tsotras University of California, Riverside Outline Background What are FPGAs MultithreadedMore information
2. Compressing data to reduce the amount of transmitted data (e.g., to save money).
Presentation Layer The presentation layer is concerned with preserving the meaning of information sent across a network. The presentation layer may represent (encode) the data in various ways (e.g., dataMore information
The relationship of a trees to a graph is very important in solving many problems in Maths and Computer Science
Trees Mathematically speaking trees are a special class of a graph. The relationship of a trees to a graph is very important in solving many problems in Maths and Computer Science However, in computerMore information
Mass Storage Structure
Mass Storage Structure 12 CHAPTER Practice Exercises 12.1 The accelerating seek described in Exercise 12.3 is typical of hard-disk drives. By contrast, floppy disks (and many hard disks manufactured beforeMore information
Microsoft Access Basics
Microsoft Access Basics 2006 ipic Development Group, LLC Authored by James D Ballotti Microsoft, Access, Excel, Word, and Office are registered trademarks of the Microsoft Corporation Version 1 - RevisionMore information
Binary Search Trees. A Generic Tree. Binary Trees. Nodes in a binary search tree ( B-S-T) are of the form. P parent. Key. Satellite data L R
Binary Search Trees A Generic Tree Nodes in a binary search tree ( B-S-T) are of the form P parent Key A Satellite data L R B C D E F G H I J The B-S-T has a root node which is the only node whose parentMore information
Algorithms and Data Structures
Algorithm Analysis Page 1 BFH-TI: Softwareschule Schweiz Algorithm Analysis Dr. CAS SD01 Algorithm Analysis Page 2 Outline Course and Textbook Overview Analysis of Algorithm Pseudo-Code and Primitive OperationsMore information
Distributed Aggregation in Cloud Databases. By: Aparna Tiwari email@example.com
Distributed Aggregation in Cloud Databases By: Aparna Tiwari firstname.lastname@example.com ABSTRACT Data intensive applications rely heavily on aggregation functions for extraction of data according to user requirements.More information
Introduction to DBMS
CHAPTER 1 Introduction to DBMS In this chapter, you will learn 1.0 Introduction 1.1 History of Database Management System 1.2 Database Architecture 1.3 Database Management System Users 1.4 Role of DBMSMore information
Efficient Retrieval of Partial Documents
Efficient Retrieval of Partial Documents Justin Zobel Alistair Moffat Ross Wilkinson Ron Sacks-Davis June 1994 Abstract Management and retrieval of large volumes of text can be expensive in both spaceMore information
Sorting revisited. Build the binary search tree: O(n^2) Traverse the binary tree: O(n) Total: O(n^2) + O(n) = O(n^2)
Sorting revisited How did we use a binary search tree to sort an array of elements? Tree Sort Algorithm Given: An array of elements to sort 1. Build a binary search tree out of the elements 2. TraverseMore information
Information Theory and Coding Prof. S. N. Merchant Department of Electrical Engineering Indian Institute of Technology, Bombay
Information Theory and Coding Prof. S. N. Merchant Department of Electrical Engineering Indian Institute of Technology, Bombay Lecture - 17 Shannon-Fano-Elias Coding and Introduction to Arithmetic CodingMore information
Searching and Sorting Algorithms
Searching and Sorting Algorithms CS117, Fall 2004 Supplementary Lecture Notes Written by Amy Csizmar Dalal 1 Introduction How do you find someone s phone number in the phone book? How do you find yourMore information
Bootstrapping Big Data
Bootstrapping Big Data Ariel Kleiner Ameet Talwalkar Purnamrita Sarkar Michael I. Jordan Computer Science Division University of California, Berkeley {akleiner, ameet, psarkar, firstname.lastname@example.com information
and the bitplane representing the second most significant bits is and the bitplane representing the least significant bits is
1 7. BITPLANE GENERATION The integer wavelet transform (IWT) is transformed into bitplanes before coding. The sign bitplane is generated based on the polarity of elements of the transform. The absoluteMore information
Attaining EDF Task Scheduling with O(1) Time Complexity
Attaining EDF Task Scheduling with O(1) Time Complexity Verber Domen University of Maribor, Faculty of Electrical Engineering and Computer Sciences, Maribor, Slovenia (e-mail: firstname.lastname@example.com) Abstract:More information
A Performance Study of Load Balancing Strategies for Approximate String Matching on an MPI Heterogeneous System Environment
A Performance Study of Load Balancing Strategies for Approximate String Matching on an MPI Heterogeneous System Environment Panagiotis D. Michailidis and Konstantinos G. Margaritis Parallel and DistributedMore information
CSC2420 Fall 2012: Algorithm Design, Analysis and Theory
CSC2420 Fall 2012: Algorithm Design, Analysis and Theory Allan Borodin November 15, 2012; Lecture 10 1 / 27 Randomized online bipartite matching and the adwords problem. We briefly return to online algorithmsMore information
An Adaptive Index Structure for High-Dimensional Similarity Search
An Adaptive Index Structure for High-Dimensional Similarity Search Abstract A practical method for creating a high dimensional index structure that adapts to the data distribution and scales well withMore information
Optimizing Description Logic Subsumption
Topics in Knowledge Representation and Reasoning Optimizing Description Logic Subsumption Maryam Fazel-Zarandi Company Department of Computer Science University of Toronto Outline Introduction OptimizationMore information
Seeking Fast, Durable Data Management: A Database System and Persistent Storage Benchmark
Seeking Fast, Durable Data Management: A Database System and Persistent Storage Benchmark In-memory database systems (IMDSs) eliminate much of the performance latency associated with traditional on-diskMore information
Oracle Rdb Performance Management Guide
Oracle Rdb Performance Management Guide Solving the Five Most Common Problems with Rdb Application Performance and Availability White Paper ALI Database Consultants 803-648-5931 www.aliconsultants.comMore information


text:
Welcome to my digital home where you can find conversations about the big ideas – the ones that really matter to us, and to all of humanity.
I would like to reconnect you to a space-age Celestial God so you can build a faith powerful enough to change your physical world.
Join me to discover a new paradigm for a 21stCentury kind of faith, one that will reconcile traditional Christianity to space age exploration and quantum theory.
Reviews on my book:
–Kirkus Reviews:
"A passionate rereading of Christianity and the nature of personal faith. Familiar concepts, sure, but Rozek's unconventional perspective makes them seem invigoratingly new."
–ForeWord Reviews
"This mash-up of Bible plus sci-fi plus metaphysics introduces new lines of thought for meditation and consideration."

subset: commoncrawl


text:
I just wanted to bring something up. Whether or not you see it as being positive or not is up to you.
The Xbox One multimedia distraction from gaming isn't really a relevant argument.
PS3 is always praised for having media playback. Why doesn't Xbox One get credit for playing media?
I just wanted to make it clear that focus on TV or any of that other stuff is not the main focus. They're just side projects that the machine can do without any extra effort.
PS4 does all the media stuff, too, so I don't really see how Microsoft bringing it up would really be a bad thing.
Samething with Nintendo. They've ALWAYS been about games first. Sega was actually the first console that brought up media in the form of hardware editions with the Sega CD. Sony continued Sega's trend long after Dreamcast has died.
Granted, the gaming machines we have today have been greatly effected by Sega and Sony, but not to the extent that such features stick around without other companies enforcing them.
Microsoft stating that bluray, TV, etc. non gaming features makes an impact, whether you think so or not. I say this, is because the sort of decisions Nintendo gets bashed for are not doing what Sony does.
"No DVD, CDs, bluray. WTF Nintendo". I just find it interesting that Nintendo gets criticised for not doing exactly what Sony does, but Microsoft gets criticised for doing what Sony does by different means.
3DS Friend Code: 4253-3737-8064 | Nintendo Network ID: Children


text:
FLORENCE, Kentucky – Lewis County Judge Executive Thomas Massie, Republican candidate for Congress in Kentucky's 4th District, today received the coveted and consequential endorsement of U.S. Senator Rand Paul. The endorsement takes the form of a television ad to run on broadcast and cable television in the Commonwealth.
In making public his endorsement of Massie, Senator Paul issued the following statement, which also is the script of the television advertisement:
"I don't like anyone telling me how to vote. I make up my own mind, and vote for the candidate who best supports term limits, balanced budgets, and the Constitution. Without question' I think Thomas Massie best fits that description.
"Thomas Massie is not a career politician. He's a taxpayer, a businessman who's concerned that the debt threatens our future.
"Thomas Massie will make a difference in Washington."
Massie, for his part, issued the following statement of praise and appreciation:
"I thank Dr. Paul for his support, which will inspire conservatives to rally around my candidacy. As Senator, Rand Paul has exceeded my expectations and those of millions of conservatives nationwide while still staying true to the values of our beloved Kentucky. I look forward to working with Senator Paul while in Congress to advance our shared principles of fiscal responsibility and constitutionally-limited government."
This ad will run on television throughout the coming week.


text:
This was an attempt at spring; braving a bright spring jumper with my summer shirt. This bag has been long missed too, having been tucked away for a good (counting in head) 7-8 months now! Unacceptable I know! Wow time flies. I brought this baby home myself, by hand, all the way from New York. Oh New York how I miss you!
This pair of trousers is actually exactly the same as the grey pair as worn in "A Personal New Years", which I didn't realise until I was putting it on! I much prefer this pair - black is always a yes for me!
I'm wearing: Reiss Scarf, Topshop Jumper, Nude DP Shirt, H&M Trousers, River Island Boots and Charles Jourdan Duffle Bag.


text:
As of 2015, online troubleshooting assistance for Caterpillar products is available at Cat.com. Caterpillar's website offers service and maintenance manuals, maintenance and troubleshooting videos, and customer service contact information.
Once on the Caterpillar homepage, click on the Support menu category and the Maintenance & Support subcategory. Categories on the Maintenance & Support page include Service, Parts & Maintenance, Repair Service Center and Electric Power Product Support. Each category opens in a new page.
For customer service contact information, choose the Contact Us subcategory from the Support category. Click on the Contact Caterpillar button to view Caterpillar's toll-free phone number or to submit a customer service request form.


text:
Wild's Cooke issues statement on Barrie hitby Dan Myers
ST. PAUL, Minn. -- Minnesota Wild forward Matt Cooke made his first public statement since his knee-on-knee hit injured Colorado Avalanche defenseman Tyson Barrie in Game 3 of their Western Conference First Round series Monday at Xcel Energy Center.
Cooke was suspended seven games Wednesday by the NHL Department of Player Safety as a result of the hit. Barrie is expected to miss 4-6 weeks with an MCL injury in his left knee.
"First and foremost, I want to say that I am disappointed and sorry that Tyson Barrie cannot play for the Colorado Avalanche tonight. I wish he could. Unfortunately, it was not my intent to collide with him knee-on-knee. It was my intent to finish my check," Cooke said. "The playoffs are a hard and physical time and it's my job to be physical. I've led my teams in hits all three games and it's an intense time. I've led my team this year in hits, and in this series.
"Since March 20, 2011, I've been a changed player. I've approached the game differently. I think differently about the game. The stats I've collected over those three seasons prove that I am a changed player. And the plays that I make and the plays that I don't make prove to that point as well.
"At the end of the day, this situation was not my intent."
The suspension was the sixth of his NHL career but first in three years.
Game 4 of the series is Thursday at Xcel Energy Center in Minnesota (9:30 p.m. ET; CNBC, TSN2, RDS2, ALT, FS-N, FS-WI). Colorado leads the best-of-7 series 2-1.


text:
Herb Formulas Notebook
Si Wei Xiang Ru Yin
Four Ingredient Mosla Powder<< Close Window
Source: Book to Safeguard Life Arranged According to Pattern (1108)
Category: Formulas that Dispel Summerheat
Pattern: Yin Summerheat, or Exterior Cold with Interior Dampness turning into Heat during the summer
Key Symptoms: Thirst, irritability, chills with skin that warm to the touch, absence of sweating, heaviness in the head, headache, abdominal pain, vomiting, diarrhoea, a stifling sensation in the chest, fatigued extremities
Tongue: White, greasy tongue coating, may have reddish body
Pulse: Floating
|Xiang Ru
|Bai Bian Dou
|(dry fried)
|Hou Po
|(Ginger fried)
|Huang Lian
|(Ginger juice fried)
Preparation: Grind into a coarse powder and take 9g as a draft. Traditionally taken with a small amount of wine is added to the draft and taken cold. May also be prepared as a decoction with the dosages above.
Actions: Releases the Exterior, scatters Cold, transforms Dampness, harmonises the Middle Jiao, clears Heat
Research Links:
Science Direct
Google Scholar
Journal of Chinese Medicine
American Dragon
Reference Notes: (click to display)
Most formulas are found in Scheid, Bensky, Ellis & Barolet (2009): Chinese Herbal Medicine: Formulas & Strategies and Chen & Chen (2015) Chinese Herbal Formulas and Applications. Others are from translations of primary sources. It is recommended that the original material is cross-referenced for mistakes and additional information.
Substitutions have been taken from Ken Lloyd & Prof. Leung (2004): Mayway UK Substitution List or the above publications and are intended as suggestions to help navigate the tight restrictions in the UK quickly. More applicable substitutions may be appropriate in specific situations.
Individual herb information has initially been sourced from TCM Wiki and American Dragon for basic data and then updated manually with my own notes.
These pages are intended to assist clinicians and are not intended for self-diagnosis or treatment for which a qualified professional should be consulted.


text:
Caroline Brown
Caroline Brown made a name for herself in Knoxville as an All-SEC soccer player for the Tennessee Lady Vols. However, little do people know that she went on to play at a higher level: in the French women's professional league, finishing as the second leading scorer for ASPTT Albi. That capped an amazing soccer career for Brown, who was named the third best underclassmen in the SEC in 2012 and as one of the Top 25 underclassmen nationally. In 2011, she was Tennessee's leading scorer and earned SEC Player-of-the-Week in late August of that year.
When it was all said and done, Coach Brown left the Lady Vols as a two-time All-SEC player, an Academic All-American, and tied for the team's all-time game winning goal scorer. She was tabbed an All-South player her senior year.
As a coach, she brings incredible knowledge of the game to pass on to the many FC Alliance players aspiring to play college soccer. Coach Brown raises the level and excitement of every practice, as she has shown a great ability to communicate to teach players of all abilities.