Systems, devices, and/or methods for managing data

This application incorporates by reference herein in its entirety, a related and concurrently filed application entitled “Systems, Devices, and/or Methods for Determining Dataset Estimators” Ser. No. 12/186,997.

United States Patent Publication 20080086444 (“Yu”), which is incorporated by reference herein in its entirety, allegedly discloses a “system and method for improving cardinality estimation in a relational database management system is provided. The method is suitable for use with a query optimizer for improved estimation of various predicates in the query optimizer's cost estimation plan by combining pre-computed statistics and information from sampled data. The system and method include sampling a relational database for generating a sample dataset and estimating cardinalities of the sample dataset. The estimated cardinalities sample datasets are reduced in accordance with the present invention by determining a first and second weight set, and minimizing a distance between the first and second weight set.” See Abstract.

U.S. Pat. No. 6,535,819 (“Clark”), which is incorporated by reference herein in its entirety, allegedly discloses “[t]he method of this invention identifies distinctive items of information from a larger body of information on the basis of similarities or dissimilarities among the items and achieves a significant increase in speed as well as the ability to balance the representativeness and diversity among the identified items by applying selection criteria to randomly chosen subsamples of all the information. The method is illustrated with reference to the compound selection requirements of medicinal chemists. Compound selection methods currently available to chemists are based on maximum or minimum dissimilarity selection or on hierarchical clustering. The method of the invention is more general and incorporates maximum and minimum dissimilarity-based selection as special cases. In addition, the number of iterations utilized to select the items is a multiple of the group size which, at its greatest, is approximately the square root of the population size. Thus, the selection method runs much faster than the methods of the prior art. Further, by adjusting the subsample size parameter K, it is possible to control the balance between representativeness and diversity in the compounds selected. In addition, the method can mimic the distributional properties of selections based on hierarchical clustering and, at least in some cases, improve upon them.” See Abstract.

Certain exemplary embodiments can provide a method, which can comprise automatically storing an estimator of properties of a dataset. The dataset can be related to any population. For example, the dataset can comprise data flows through a network node (e.g., a router), sales data, and/or marketing data, etc. The estimator can be based upon a sketch of the dataset. Estimators of the sketch can have exponentially distributed ranks.

A wide variety of potential practical and useful embodiments will be more readily understood through the following detailed description of certain exemplary embodiments, with reference to the accompanying exemplary drawings in which:

FIG. 1 is a block diagram of an exemplary embodiment of a set if graphs indicative of absolute relative errors in estimated parameters as a function of sketch size for various sketches;

FIG. 2 is a block diagram of an exemplary embodiment of a set if graphs indicative of absolute relative errors in estimated parameters as a function of sketch size for various sketches;

FIG. 3 is a block diagram of an exemplary embodiment of a system 3000 ;

FIG. 4 is a flowchart of an exemplary embodiment of a method 4000 ; and

FIG. 5 is a flowchart of an exemplary embodiment of a method 5000 ; and

FIG. 6 is a block diagram of an exemplary embodiment of an information device 6000 .

Certain exemplary embodiments can provide a method, which can comprise automatically storing an estimator of properties of a dataset. The dataset can be related to any population. For example, the dataset can comprise data flows through a network node (e.g., a router), sales data, and/or marketing data, etc. The estimator can be based upon a sketch of the dataset. Estimators of the sketch can have exponentially distributed ranks. As used herein, the phrase exponentially distributed means a random variable from an exponential distribution, that is, a distribution with probability density function: λe −λx for x>=0 and 0 for x<0.

The following indented paragraphs immediately following the present paragraph describe one or more exemplary embodiments and are illustrative and not restrictive in their scope.

A Bottom-k sketch is a summary of a set of items with nonnegative weights that supports approximate query processing. As used herein, the phrase query means (n.) a request, such as for information from a database; (v.) to request and/or obtain information, such as from a database in response to a structured request. As used herein, the phrase weight means a numeric value (non-negative real number) that is associated with an item. As used herein, the phrase value means a measured, assigned, determined, and/or calculated quantity or quality for a variable and/or parameter. As used herein, the phrase sketch means a summary of a set of items with nonnegative weights that supports approximate query processing. As used herein, the phrase item means a single article of a plurality of articles. As used herein, the phrase plurality means the state of being plural and/or more than one. As used herein, the phrase term a means at least one. A sketch is obtained by associating with each item in a ground set an independent random rank drawn from a probability distribution that depends on the weight of the item and including the k items with smallest rank value. As used herein, the phrase k th smallest means a largest value of a set of k values, the k values having smaller values than other values of a set. As used herein, the phrase rank means an independent random variable assigned to an item that is drawn from a distribution that depends on the weight of the item. As used herein, the phrase obtain means to receive, get, take possession of, procure, acquire, calculate, determine, and/or compute. As used herein, the phrase from means used to indicate a source. As used herein, the phrase each means every one of a group considered individually. Bottom-k sketches are an alternative to k-mins sketches, which consist of the k minimum ranked items in k independent rank assignments, and of min-hash sketches, where hash functions replace random rank assignments. As used herein, the phrase replace means to substitute one thing for another. Sketches support approximate aggregations, including weight and selectivity of a subpopulation. As used herein, the phrase subpopulation means a portion of a larger set of data and/or entities. As used herein, the phrase selectivity means a fraction of items that satisfy a given predicate regarding items attribute values. Coordinated sketches of multiple subsets over the same ground set support subset-relation queries such as Jaccard similarity or the weight of the union. As used herein, the phrase coordinate means to interact regarding movements and/or functions. As used herein, the phrase union means a set containing all and only the members of two or more given sets. As used herein, the phrase subset means a portion of a set. All-distances sketches are applicable for datasets where items lie in some metric space such as data streams (time) or networks. As used herein, the phrase distance means a measure of physical and/or logical separation. As used herein, the phrase data means information represented in a form suitable for processing by an information device. As used herein, the phrase information means facts, terms, concepts, phrases, expressions, commands, numbers, characters, and/or symbols, etc., that are related to a subject. Sometimes used synonymously with data, and sometimes used to describe organized, transformed, and/or processed data. It is generally possible to automate certain activities involving the management, organization, storage, transformation, communication, and/or presentation of information. As used herein, the phrase store means to place, hold, and/or retain in a memory. As used herein, the phrase device means a machine, manufacture, and/or collection thereof. As used herein, the phrase dataset means a relatively large body of information represented in a form suitable for processing by an information device. These sketches compactly encode the respective plain sketches of all neighborhoods of a location. As used herein, the phrase neighborhood means a nearby area within a set maximum distance from a reference location. As used herein, the phrase location means a place. These sketches support queries posed over time windows or neighborhoods and time/spatially decaying aggregates. An important advantage of bottom-k sketches is much tighter estimators for several basic aggregates. As used herein, the phrase estimator means a statistical and/or calculable parameter associated with a population and/or a sub-population. To materialize this benefit, we can adapt traditional k-mins applications to use bottom-k sketches. As used herein, the phrase can means is capable of, in at least some embodiments. As used herein, the phrase application means a set of computer-readable instructions and/or a computer program. As used herein, the phrase compute means to calculate, estimate, determine, and/or ascertain via a processor. As used herein, the phrase via means by way of and/or utilizing. As used herein, the phrase determine means to find and/or decide upon. As used herein, the phrase estimate means (n.) a calculated value approximating an actual value; (v.) to calculate and/or determine approximately and/or tentatively. We propose all-distances bottom-k sketches and develop and analyze data structures that incrementally construct bottom-k sketches and all-distances bottom-k sketches. As used herein, the phrase bottom-k sketch means a summary of a set of items with nonnegative weights that supports approximate query processing. The summary contains k items. The distribution of items included in the sketch corresponds to associating independent random rank values that are drawn from a probability distribution parametrized by the weight for each item, and taking the k items with smallest rank value. As used herein, the phrase correspond means to be related, associated, accompanying, similar in purpose and/or position, conforming in every respect, and/or equivalent and/or agreeing in amount, quantity, magnitude, quality, and/or degree. As used herein, the phrase all-distance bottom-k sketch means a compact encoding of plain bottom-k sketches of neighborhoods of a certain location in which, for a given distance, the sketch in a neighborhood within the given distance of the location can be constructed from the all-distances sketch. Another advantage of bottom-k sketches is that when the data is represented explicitly, they can be obtained much more efficiently than k-mins sketches. We show that k-mins sketches can be derived from respective bottom-k sketches, which enables the use of bottom-k sketches with off-the-shelf k-mins estimators (In fact, we obtain tighter estimators since each bottom-k sketch is a distribution over k-mins sketches). As used herein, the phrase derive means obtain via determining, calculating, and/or looking-up. Sketching or sampling is an extremely useful tool for storage and queries on massive datasets. Sketches allow us to process approximate queries on the original datasets while occupying a fraction of the storage space utilized for the full dataset and using a fraction of the computation resources utilized for the exact answer. As used herein the phrase answer means (n.) a reply and/or response; (v.) to reply. The value of a sketching method depends on the efficiency of its implementation, its versatility in terms of the operations supported, and the quality of the estimates obtained. Bottom-k and k-mins sketches are summaries of a set of items with positive weights. k-mins sketches (The min-rank method) are obtained by assigning independent random ranks to items where the distribution used for each item depends on the weight of the item. We retain the minimum rank of an item in the set. This is repeated with k independent rank assignments for some integer k≧1 and we obtain a k-vector of independent minimum ranks and k independent weighted samples. Bottom-k sketches are an emerging alternative to k-mins sketches. Bottom-k sketches are constructed using a single rank assignment. The bottom-k sketch of a subset contains the k items with smallest ranks in the subset. The sketch supports approximate query processing over the original dataset and subpopulations of this dataset. Basic aggregations include the weight of the set or the selectivity of a subpopulation (subset) of the set and derived aggregations include approximate quantiles, average weight, and variance and higher moments. As used herein, the phrase variance means a measure of variation of a set of observations defined by a sum of the squares of deviations from a mean, divided by a number of degrees of freedom in the set of observations. The sketch of a set is a weighted random sample. When used with exponentially distributed ranks, bottom-k sketches are a weighted sample without replacement ( WS -sketches) whereas k-mins sketches are a weighted sample with replacement ( WSR -sketches). In applications where there are multiple subsets that are defined over the same ground set of items, a sketch is produced for each subset. As used herein, the phrase define means to establish the meaning, relationship, outline, form, and/or structure of; and/or to precisely and/or distinctly describe and/or specify. The sketches of different subsets are “coordinated,” sharing the same rank assignments to the items of the ground set, and support queries over subset relations, such as the weight of the union or intersection, their weight ratio, and resemblance or Jaccard similarity coefficient. As used herein, the phrase different means changed, distinct, and/or separate. As used herein, the phrase Jaccard similarity means a quantitative measure of resemblance. A useful property of “coordinated” sketches is that the sketch of a union can be computed from the sketches of the subsets. As used herein, the phrase property means a parameter associated with a characteristic. Therefore, given sketches of subsets, we can perform aggregations on unions of subsets. As used herein, the phrase perform means to begin, take action, do, fulfill, accomplish, carry out, and/or complete, such as in accordance with one or more criterion. Example of an application with multiple subsets is when items are associated with nodes of a directed graph and we compute k-mins sketches for the reachability set of each node. As used herein, the phrase node, with the exception of network node devices, means a related subset of values of a dataset. As used herein, the phrase associated with means related to. These sketches can be computed in Õ(km) time (and storage) whereas an explicit representation of the subsets utilizes O(mn) time. Applications include maintaining a sketch of influencing events for each process in a computer system, when a process A affects process B, the new sketch of B becomes the sketch of the union; and using the property that the sketches reduce the approximate sum problem to that of finding a minimum. In certain exemplary embodiments, k-mins sketches can be used for aggregations on gossip networks. As used herein, the phrase sum means (n.) a total obtained via the addition of a plurality of values; (v.) to add. As used herein, the phrase new means having been made, defined, determined, and/or coming into existence relatively recently as compared to something else. As used herein, the phrase maintain means to retain, preserve, sustain, keep in an existing state, and/or continue to obtain. Other applications with multiple subsets where sketches support fast computation of subset relations are near-duplicate detection for Web pages (a sketch is produced for each Web page), study of similar Web sites, mining of association rules from market basket data, and eliminating redundant network traffic. As used herein, the phrase market means (n.) a commercial activity; (v.) to encourage buyers and/or to attempt to sell. In these applications, a variant termed min-hash sketches substitutes random rank assignments with random hash functions (families of min-wise independent hash functions or ε-min-wise functions). With random hash functions, the rank assignment of an item depends on the item identifier, and it has the property that all copies of the same item across different subsets obtain the same rank, without additional book keeping or coordination between all occurrences of each item. As used herein, the phrase between means in a separating interval and/or intermediate to. This allows for efficient aggregations over distinct occurrences (see) and supports subset-relation queries. Bottom-k sketches encode more information than k-mins sketches. (Intuitively, sampling without replacement is more informative than sampling with replacement). In certain exemplary embodiments, bottom-k sketches can be superior to k-mins sketches in terms of estimate quality. Estimators for subpopulation weight using priority ranks ( PRI -sketches) can be provided and estimators for general families of rank functions can be provided. As used herein, the phrase provide means to furnish, supply, give, convey, send, and/or make available. The improvement in estimate quality is significant on weight distributions and values of k, such that items are likely to be sampled multiple times in a k-sample drawn with replacement, such as skewed Zipf-like distributions that often arise in practice. For subset relations such as the weight of the intersection or union, bottom-k sketches improve over k-mins sketches even when weights are uniform: Carefully designed estimators are applied to the combined bottom-k sketches, which reveal more members of the union and intersection than two corresponding k-mins sketches. As used herein, the phrase applied means incident directly and/or indirectly upon. We facilitate the use of bottom-k sketches by developing and analyzing data structures that construct these sketches. Our results allow applications that use k-mins sketches to use the superior bottom-k sketches. An inherent difference we had to tackle is that k-mins sketches are obtained using k independent rank functions, which allows for k independent copies of the same simple data structure to be used whereas bottom-k entries are dependent. Sketches are constructed incrementally as items are processed. The sketch is manipulated through two basic operations: A test operation which tests if the sketch has to be updated, and an update operation which inserts the new item if the sketch indeed has to be updated. As used herein, the phrase update means to make current. As used herein, the phrase test means to evaluate. As used herein, the phrase through means in one side and out the opposite or another side of, across, among, and/or between. We make this distinction since test operations can be performed much more efficiently than update operations. The number of update operations depends on the order in which items are processed and on the weight distribution of the data. As used herein, the phrase order means a degree in a continuum of size or quantity. As used herein, the phrase size means physical dimensions, proportions, magnitude, amount, and/or extent of an entity. The number of test operations is typically larger than the number of updates. The extent in which it is larger, however, highly depends on the application. We distinguish between applications with explicit representation or implicit representation of the data. In applications with an explicit representation, item-subset pairs are provided explicitly. The dataset could be distributed, presented as a data stream, or in external memory, but the pairs are explicitly provided and are all processed to produce the sketches. In applications with implicit representation, the subsets are specified as neighborhoods in a graph or some metric space. With explicit representation, the number of test operations is much larger than the number of update operations. We analyze the number of test and update operations and how it depends on the way the data is presented and on the distribution of the item weights. All-distances sketches are a generalization of plain sketches that are used when the underlying dataset has items associated with locations in some metric space, and subsets are specified by neighborhoods of a location. All-distances k-mins sketches were used for data streams (where aggregation is over windows of elapsed time to the present time), the Euclidean plane (where we are presented with a query point and distance), a graph (the query is a node and distance), or distributed “spatial aggregation” over a network. An all-distances sketch is a compact encoding of the plain sketches of all neighborhoods of a certain location q. For a given distance d, the sketch for the d-neighborhood of the location can be constructed from the all-distances sketch. All-distances sketches also support time-decaying and spatially-decaying aggregates using arbitrary decay functions. As used herein, the phrase arbitrary means not necessarily conforming to a predetermined structure. As used herein, the phrase predetermined means determine, decide, or establish in advance. Certain exemplary embodiments define bottom-k all-distances sketches and present efficient data structures for maintaining both all-distances k-mins sketches and all-distances bottom-k sketches. We analyze the number of operations utilized to construct all-distances sketches under different arrival orders of the items. We provide a method to derive WSR -sketches (k-mins with exponential ranks) from WS -sketches (bottom-k with exponential ranks). This mimicking process provides a general method of applying estimators designed for WSR -sketches to WS -sketches. This process enables us to use bottom-k sketches in applications (such as those with explicit representation of the data) where they can be obtained much more efficiently than k-mins sketches and use readily available WSR -sketches estimators. In fact, since each WS -sketch corresponds to a distribution over WSR -sketches, we obtain estimators with smaller variance than the underlying WSR -sketches estimators. This reduction also shows that WS -sketches are strictly superior to WSR -sketches. We provide examples of applications of the mimicking process. Let I be a ground set of items, where item iεI has weight w(i)≧0. A rank assignment maps each item i to a random rank r(i). The ranks of items are drawn independently using a family of distributions f w , (w≧0), where the rank of an item with weight w(i) is drawn according to f w(i) . We use random rank assignments to obtain sketches of subsets as follows. For a subset J of items and a rank assignment r we define B 1 (r,J)=argmin jεJ (j), to be the item in J with smallest rank according to r. For iε{1, . . . , |J|}, we define B i (r,J) to be the item in J with i th smallest rank according to r and r i (J)≡r(B i (r,J)) to be the i th smallest rank value in J according to r. Definition 1. k-mins sketches are produced from k independent rank assignments, r (1) , . . . , r (k) . The k-mins sketch of a subset J is the k-vector (r 1 (1) (J), r 1 (2) (J), . . . , r 1 (k) (J)). To support some queries, we may need to include with each entry an identifier or some other attributes such as the weight of the items B 1 (r (j) ,J) (j=1, . . . , k). As used herein, the phrase may means is allowed and/or permitted to, in at least some embodiments. Definition 2. Bottom-k sketches are produced from a single rank assignment r. The bottom-k sketch s(r,J) of the subset J is a list of entries (r i (J), w(B i (r,J))) for i=1, . . . , k. The list is ordered by rank, from smallest to largest. The bottom-k sketch of a subset is therefore a list with up to k entries. The size of the list is the minimum of k and the number of items in the subset. For a single item i (a subset of size 1), the bottom-k sketch is a list with a single entry (r 1 (J), w(B 1 (r,J))). To support queries, in addition to the weight, entries in the sketch may include an identifier and attribute values of items B i (r,J) (i=1, . . . , k). Bottom-k and k-mins sketches have the following useful property: The sketch of a union of two sets can be generated from the sketches of the two sets. Let J and H be two subsets. As used herein, the phrase generate means to create, produce, render, give rise to, and/or bring into existence. For any rank assignment r, r 1 (J∪H)=min{r 1 (J),r 1 (H)}. Therefore, for k-mins sketches we have (r 1 (1) (J∪H), . . . , r 1 (k) (J∪H))=(min{r 1 (1) (J), r 1 (1) (H)}, . . . , min{r 1 (k) (J), r 1 (k) (H)}). For bottom-k sketches, the k smallest ranks in the union J∪H are contained in the union of the sets of the k-smallest ranks in each of J and H. That is, s(r,J∪H)⊂s(r,J)∪s(r,H). Therefore, the bottom-k sketch of J∪H can be computed by taking the entries with k smallest ranks in the combined sketches of J and H. To support sketch-based set operations and queries, we need to store the rank values of items. To perform sketch-based queries on a single subset, however, we do not need all rank values. With bottom-k sketches, it is sufficient to store the (k+1)st smallest rank value, r k+1 : We (re)draw random rank values for each item i in the sketch using f w(i) conditioned on the rank being smaller than r k+1 . This is just like (re)drawing a random bottom-k sketch from the probability subspace where the minimum rank of items not in the sketch is equal to r k+1 and all items in the sketch have ranks smaller than r k+1 . Beyond reduced storage, this observation often enables us to obtain tighter estimators. The unbiased rank conditioning estimator for subpopulation weight is applied to the value r k+1 and the weights of the items in the (unordered) sketch. As used herein, the phrase unbiased means characterized by a lack of partiality. In some cases, however, it is easier to derive estimator that is applied to the ordered sketch with rank values (the mimicking process is applied to an ordered bottom-k sketch). In this case, instead of applying an estimator to the original sketch and rank values, we take its expectation over re-drawn sketches or its average over multiple draws (if the expectation is hard to compute). As used herein, the phrase expectation means a statistical mean value. This results in an estimator with at most the same variance and often smaller variance. Correctness follows from a basic property of variances: Lemma 1. Let a 1 and a 2 be two random variables over Ω. Suppose there is a partition of Ω such that the value of a 2 on each part is equal to the expectation of a 1 on that part. Then var(a 2 )≦var(a 1 ). The choice of which family of random rank functions to use matters only when items are weighted. Otherwise, sketches produced using one rank function can be transformed to any other rank function. We assume to simplify the analysis that all random values are distinct WS -sketches and WSR -sketches. A convenient choice for the rank function f w is an exponential distribution with parameter w. The density function of this distribution is f w (x)=we −wx , and its cumulative distribution function is F w (x)=1−e −wx . We refer to k-mins sketches with these ranks as WSR -sketches and to bottom-k sketches with these ranks as WS -sketches. The minimum rank r 1 (J) of an item in a subset J⊂I is exponentially distributed with parameter w(J)=Σ iεJ w(i). This follows from the fact that the minimum of random variables each drawn from an exponential distribution is also an exponentially distributed random variable with parameter equal to the sum of the parameters of these distributions. The item with the minimum rank B 1 (r,J) is a weighted random sample from J: The probability that an item iεJ is the minimum rank item is w(i)|w(J). Therefore we can conclude that a WSR -sketch of size k of a subset J is a weighted random sample of size k, drawn with replacement from J (hence the term WSR -sketches). The ranks of these items is a set of k independent samples from an exponential distribution with parameter w(J). Hence, if the weight w(J) is provided and we do not use subset-relation queries rank values are redundant. If w(J) is not provided, the rank values can be used in unbiased estimators for both w(J) and the inverse weight 1/w(J). Estimators for the inverse-weight are useful for obtaining unbiased estimates for quantities where the weight appears in the denominator. These include weight ratio of two different subsets, set resemblance of two subsets, and average weight of a subset. On the other hand, the items in a WS -sketch are samples drawn without replacement from J: Lemma 2. A WS -sketch of size k of a subset J is a sample of size k drawn without replacement from J. Proof. The probability that item iεJ is B 1 (r,J) is w(i)/w(J). Conditioned on the bottom-j ranked items in J being i 1 , . . . , i j , B j+1 (r,J) is iεJ, {i 1 , . . . , i j } with probability

if items have uniform weights and presented in a fixed but arbitrary order or if items are weighted and presented in a random order, the expected number of updates to the minimum rank is ≦ln s; and if items are weighted and presented in a fixed but arbitrary order and the family of rank functions is c-moderate, the expected number of updates is O(log(max i w(i)/min i w(i))log s).

It follows that the total number of updates when computing k-mins sketches of all reachability sets is O(kn log n) for uniform weights and weighted items presented in random order and

O(kn log(max i w(i)/min i w(i))log n) for weighted items presented in arbitrary order. We perform a test or update in O(1) time and the number of tests is at most m/n times the number of updates. Therefore, the total time is m/n times the number of updates.

The number of updates for bottom-k sketches is given in Lemmas 1, 2, and 4. Each update takes O(log k) time, and a test takes O(1) time. The number of tests is m/n times the number of updates. Therefore, the total time is O(log k+m/n) times the number of updates given in each of these lemmas.

An all-distances sketch is an encoding of plain sketches of all neighborhoods of a certain location q. For a given distance d, the sketch for the d-neighborhood of the location can be retrieved from the all-distances sketch.

We review k-mins all-distances sketches and introduce bottom-k all-distances sketches. We consider the size of the all-distances sketches, its construction time, and the time it takes to retrieve the sketch of a particular distance. We consider incremental construction, where current all-distances sketches are maintained and updated upon the arrival of new information (item, distance, rank). The operations we consider are test that determines if the current sketch needs to be modified when new information arrives, update of the current sketch, and a distance query issued to the final sketch. The distance query retrieves from the all-distances sketch the plain sketch for the neighborhood of the location q specified by the query distance.

We show that the expected size of the representation of the all-distances bottom-k sketch matches that of the k-mins sketch. When subsets are represented explicitly, the computation time of the all-distances bottom-k sketches is about factor of k faster than that of the all-distances k-mins sketches. When subsets are represented via a graph, the construction times are comparable.

All-distances k-mins sketches: We review all-distances k-mins sketches. Consider a single rank assignment. An MV/D list of a location q (Minimum Value/Distance List) encodes the minimum rank in any neighborhood (query distance) of q in a compact way. It is a list of triples where each triple contains an item e, its rank, and its distance from q. An item e is in the MV/D list of q if there is no item with smaller rank closer to q. The MV/D list is sorted in increasing distance and decreasing rank order. For a query distance d, the smallest rank of an item in the MV/D list of q of distance at most d from q is the item of smallest rank in the subset of items in the d-neighborhood of q. The expected size of the list depends on the rank function and on the weight distribution of the items.

Lemma 7. The size of an MV/D list of n weighted items from a location q is bounded as follows:

when weights are uniform, the expected size is O(log n); if weights are arbitrary but items are assigned to locations at random then the expected size over assignments of items to locations, and over rank assignments is O(log n); and if items have arbitrary weights and placed in arbitrary locations and ranks are assigned using a c-moderate family of rank functions for some constant c, then the expected size is O(log(max i w(i)/min i w(i))log n).

when items are presented in random order and there are uniform weights, the expected number of updates is O(log 2 n); if items are assigned to locations at random, the expected number of updates to the MV/D list, over assignments of items to locations, rank assignments, and presentation order of items is O(log 2 n); and if ranks are assigned using a c-moderate family of rank functions for some constant c, then the expected number of updates to the MV/D list, over rank assignments, and presentation order of items is O(log(max i w(i)/min i w(i))log 2 n).

All-distances bottom-k sketches: An all-distances bottom-k sketch encodes the bottom-k items in a neighborhood defined by any query distance from a location q. The all-distances bottom-k sketch is a data structure that generalizes a single MV/D list. An item i, its rank value r(i), and distance d (i) are represented in the sketch if and only if the item has one of the bottom-k ranks in the d (i)-neighborhood of the location.

It is convenient to think of the all-distances bottom-k sketch as a list of lists arranged by increasing distance. For each distance d where the set of bottom-k items within distance d changes, we record the list of bottom-k items within this distance. As used herein, the phrase record means a collection of structured data elements organized by fields. A group of records forms a file, table, and/or database. For example, a record might comprise data elements stored in fields such as: a name field, an address field, and a phone number field. This list is valid until the next distance for which there is a change.

The list of lists representation, however, is not storage efficient, since all but one item is repeated in two consecutive lists. This sketch can be more compactly represented if we only record the changes to the list. Certain exemplary embodiments can utilize relatively compact representations for an all-distances bottom-k sketch that utilize storage proportional to the number of distances where the bottom-k set changes.

We bound the number of distances for which the bottom-k list changes. These bounds imply that the storage for an all-distances bottom-k sketch is comparable to the storage for k MV/D lists in all-distances k-mins sketch.

Lemma 10. Consider an all-distances bottom-k sketch for n items of a location q. We bound the expected number of distances from q where the set of bottom-k items changes.

for uniform weights, the expected number of distances is O(k log n); for a set of items with arbitrary weights that are randomly assigned to locations the expected number of distances (over assignments of items to locations, and over rank assignments) is O(k log n); and if items have arbitrary weights and placed in arbitrary locations and ranks are assigned using a c-moderate family of rank functions for some constant c, the expected number of distances is O(k log(max i w(i)/min i w(i))log n).

For a set of items with arbitrary weights and a set of locations, the expected number of distances from a location q where the set of bottom-k items changes, over assignments of items to locations, and over rank assignments is O(k log n). If items have arbitrary weights and placed in arbitrary locations and ranks are assigned using a c-moderate family of rank functions for some constant c, the expected number of distances from a location q where the set of bottom-k items changes is O(k log(max i w(i)/min i w(i))log n).

If items are presented in order of increasing distances from q we can obtain a bottom-k list for the current distance, from the bottom-k list of the previous distance by doing an insertion and a deletion. Similarly, if items arrive sorted by rank value, then the number of updates to the bottom-k sketch is proportional to the size (number of breakpoint distances) of the sketch. We can also bound the number of updates performed if items arrive in a random order.

Lemma 12. Consider the expected number of updates that is performed in an incremental construction of an all-distances bottom-k sketch of a location q when items are presented in a random order (the order is a random permutation):

when item weights are uniform, the expected number of updates is O(k log 2 n); when items have arbitrary weights, the expected number of updates over assignments of weights to locations, over rank assignments, and arrival order, is O(k log 2 n); and when items have arbitrary weights, and the family of rank functions is c-moderate, the expectation over rank assignments and arrival orders of the number of updates is O(k log(max i w(i)/min i w(i))log 2 n).

p 1 =w ( i 1 )exp(− r ( i 1 ) w ( i 1 )) w ( i 2 )exp(− r ( i 2 ) w ( i 2 )) . . . w ( i j )exp(− r ( i j ) w ( i j ))

is the probability that the minimum rank among i j+1 , . . . , i n is at least r(i j ).) Therefore, the probability density is

(we formally define r(i 0 )=0.)

The WS -sketch provides the k-prefix of the random permutation defined by the ranks. By Corollary 1 the rank differences r(i j )−r(i j−1 ) are k independent samples where the j th sample is from an exponential distribution with parameter

The first entry of the mimicked sketch contains the item i 1 with rank value r(i 1 ). Suppose items i 1 , . . . , i j (j≧1) are drawn (at least once). The next entry is obtained as follows:

Draw items using weighted sampling with replacement and assign independent rank values from an exponential distribution with parameter w(J) until: k samples are obtained (for mimicked wsr-sketches) or the (k+1) st distinct item is sampled (for mimicked wsrd-sketches). Generate a rank assignment and obtain the corresponding ws-sketch b of size k. Draw a mimicked sketch from M(b). Generate a rank assignment and obtain the corresponding WS -sketch b of size k. Draw a WS -sketch b′εL(b). Draw a mimicked sketch from M(b′).

FIG. 3 is a block diagram of an exemplary embodiment of a system 3000 , which can comprise an information device 3100 . As used herein, the phrase comprise means to include, but not be limited to, what follows. Information device 3100 can be communicatively coupled to a server 3300 via a network 3200 . As used herein, the phrase couple means to join, connect, and/or link two things together. As used herein, the phrase network means a communicatively coupled plurality of nodes, communication devices, and/or information devices. Via a network, such devices can be linked, such as via various wireline and/or wireless media, such as cables, telephone lines, power lines, optical fibers, radio waves, and/or light beams, etc., to share resources (such as printers and/or memory devices), exchange files, and/or allow electronic communications therebetween. A network can be and/or can utilize any of a wide variety of sub-networks and/or protocols, such as a circuit switched, public-switched, packet switched, connection-less, wireless, virtual, radio, data, telephone, twisted pair, POTS, non-POTS, DSL, cellular, telecommunications, video distribution, cable, terrestrial, microwave, broadcast, satellite, broadband, corporate, global, national, regional, wide area, backbone, packet-switched TCP/IP, IEEE 802.03, Ethernet, Fast Ethernet, Token Ring, local area, wide area, IP, public Internet, intranet, private, ATM, Ultra Wide Band (UWB), Wi-Fi, BlueTooth, Airport, IEEE 802.11, IEEE 802.11a, IEEE 802.11b, IEEE 802.11g, X-10, electrical power, multi-domain, and/or multi-zone sub-network and/or protocol, one or more Internet service providers, and/or one or more information devices, such as a switch, router, and/or gateway not directly connected to a local area network, etc., and/or any equivalents thereof.

As used herein, the phrase router means a device adapted to direct traffic and/or determine the next network point to which a data packet should be forwarded enroute toward its destination. The router is connected to at least two networks and determines which way to send each data packet based on its current understanding of the state of the networks it is connected to. Routers create or maintain a table of the available routes and use this information to determine the best route for a given data packet. Examples include a router, route-reflector, route server, server-based router, router-switch, sets of routers, and/or intra-networking devices, etc. A typical router operates at least at the bottom 3 layers (Physical, Link, and Network layers) of the OSI model. Flow records containing this information are collected at IP routers by tools such as Cisco's NetFlow (now emerging as an IETF standard). As used herein, the phrase collect means to accumulate and/or gather. Each flow record contains the number of packets and bytes of the flow. As used herein, the phrase packets means a collection of digital data comprised of information and an associated header transmitted over a packet-switching network.

Server 3300 can comprise and/or be communicatively coupled to a user program 3320 , a user interface 3360 , and a memory device 3340 . As used herein, the phrase interface means (n) a boundary across which two independent systems meet and act on and/or communicate with each other. (v) to connect with and/or interact with by way of an interface. As used herein, the phrase memory device means an apparatus capable of storing analog or digital information, such as instructions and/or data. Examples include a non-volatile memory, volatile memory, Random Access Memory, RAM, Read Only Memory, ROM, flash memory, magnetic media, a hard disk, a floppy disk, a magnetic tape, an optical media, an optical disk, a compact disk, a CD, a digital versatile disk, a DVD, and/or a raid array, etc. The memory device can be coupled to a processor and/or can store instructions adapted to be executed by processor, such as according to an embodiment disclosed herein. Information device 3100 and/or server 3300 can be adapted to perform any method and/or activity described herein. In certain exemplary embodiments, user program 3320 can be adapted to analyze one or more datasets and/or derive one or more bottom-k sketches from a dataset. User interface 3360 can be adapted to render information regarding the dataset and/or a sketch derived therefrom.

FIG. 4 is a flowchart of an exemplary embodiment of a method 4000 . As used herein, the phrase method means a process, procedure, and/or collection of related activities for accomplishing something. In certain exemplary embodiments, any activity and/or subset of activities of method 4000 can be performed automatically by an information device. As used herein, the phrase activity means an action, act, deed, function, step, and/or process and/or a portion thereof. As used herein, the phrase automatic means performed via an information device in a manner essentially independent of influence and/or control by a user. As used herein, the phrase automatically means acting and/or operating in a manner essentially independent of external human influence and/or control. For example, an automatic light switch can turn on upon “seeing” a person in its view, without the person manually operating the light switch. In certain exemplary embodiments, one or more activities of method 4000 can be performed via machine-implementable instructions stored on a machine-readable medium. As used herein, the phrase machine implementable instructions means directions adapted to cause a machine, such as an information device, to perform one or more particular activities, operations, and/or functions. The directions, which can sometimes form an entity called a “processor”, “kernel”, “operating system”, “program”, “application”, “utility”, “subroutine”, “script”, “macro”, “file”, “project”, “module”, “library”, “class”, and/or “object”, etc., can be embodied as machine code, source code, object code, compiled code, assembled code, interpretable code, and/or executable code, etc., in hardware, firmware, and/or software. As used herein, the phrase machine-readable medium means a physical structure from which a machine, such as an information device, computer, microprocessor, and/or controller, etc., can obtain and/or store data, information, and/or instructions. Examples include memories, punch cards, and/or optically-readable forms, etc. At activity 4100 , a dataset can be sampled.

At activity 4200 , a sketch can be computed from the dataset. In certain exemplary embodiments, the sketch can be a bottom-k sketch and/or an all-distance bottom-k sketch. Calculation of the bottom-k sketch (or all-distances bottom-k sketch or k-mins sketch) can be integrated with the sampling of activity 4100 . The computation of the sketch can define a result and/or a distribution of the sampling of activity 4100 . In certain exemplary embodiments, the bottom-k data sketch can be an all-distance bottom-k sketch. The bottom-k sketch can be a coordinated sketch of a plurality of bottom-k sketches. The bottom-k sketch can comprise a single stored rank value. The ranks of the bottom-k sketch can be exponentially distributed. The bottom-k sketch can be defined with respect to a family of probability distributions that can be parametrized by weight. Exponential ranks (exponential distribution with parameter equal to the weight) can be an exemplary choice. Exponential ranks can correspond to a special sampling method of weighted sampling without replacement also known in statistics as probability proportional to size without replacement (PPSWOR). After a sketch is derived, since the dataset can be large and/or not stored, certain exemplary embodiments might not go back to the original dataset.

At activity 4300 , a new dataset item can be received. Each new item can have a weight and distance. A rank can be computed for the item and the all-distances sketch can be updated if the new item has minimum rank among all items in the sketch that are of an equal or smaller distance.

At activity 4400 , the bottom-k sketch can be updated and/or maintained responsive to received dataset information. As used herein, the phrase receive means to obtain, take, and/or acquire. The all-distance bottom-k sketch can be automatically maintained based upon new flow records outputted by a statistics collecting module associated with the dataset. As used herein, the phrase statistics collecting module means hardware, firmware, and/or software adapted to perform calculations on parameters of a population. As used herein, the phrase statistics means a numerical fact. Sketches can be updated when new items of the dataset arrive. A new item might be added to the sketch or might not. In addition, because the sketch can be a fixed size, a current item can be taken out if a new item is inserted.

Responsive to received dataset items, certain exemplary embodiments can be adapted to automatically cause the bottom-k sketch to be updated and/or update the bottom-k sketch (e.g., the all-distance bottom-k sketch). Certain exemplary embodiments can, responsive to received dataset items, automatically test the all-distance bottom-k sketch to determine whether the all-distance bottom-k sketch will be updated. Certain exemplary embodiments can, responsive to an automatic determination that a rank value of a received dataset item is less than a rank of a k th smallest current ranked item at a node that has distance that is at most that of the received item, automatically update the all-distance bottom-k sketch. As used herein, the phrase at most means less than or equal to.

At activity 4500 , the bottom-k sketch and/or estimators associated with the bottom-k dataset can be stored on a memory device. In certain exemplary embodiments, an estimator of properties of a dataset can be automatically stored. The items in the all-distance bottom-k set can be stored in order of increasing distances from a predetermined location, in order of increasing ranks, or in an arbitrary order. Certain exemplary embodiments can be adapted to, via a processor, automatically store an all-distance bottom-k sketch of a dataset on a machine-readable medium. The processor can be adapted to automatically compute estimators of the all-distance bottom-k sketch from corresponding determined estimators of a k-min sketch of the dataset. The k-min sketch can be derived from the all-distance bottom-k sketch. Certain exemplary embodiments can be adapted to, via a processor, the estimator of properties of the dataset on a machine-readable medium. The processor can be adapted to automatically compute the estimator of properties based upon computed adjusted weights of the all-distance bottom-k sketch of the dataset. The adjusted weights can be computed via a Markov-chain based method. The adjusted weights can be applied to items comprised in the bottom-k sketch. The adjusted weights can be adapted to be used to estimate a size of subpopulations of items. The bottom-k sketch can derived from the all-distance bottom-k sketch.

FIG. 5 is a flowchart of an exemplary embodiment of a method 5000 . As used herein, the phrase method means a process, procedure, and/or collection of related activities for accomplishing something. In certain exemplary embodiments, any activity and/or subset of activities of method 5000 can be performed automatically by an information device. In certain exemplary embodiments, one or more activities of method 5000 can be performed via machine-implementable instructions stored on a machine-readable medium. At activity 4100 , a query can be received. For example, the query can be related to a selectivity and/or Jaccard similarity, etc.

At activity 5200 , a k-min sketch can be derived from the bottom-k data sketch. As used herein, the phrase k-min sketch means a summary of a set of items with positive weights obtained by, repeating k times, assigning independent random ranks to items where the distribution used for each item depends on the weight of the item and taking the item with minimum rank value. k-mins sketches can represent another form of sampling, which can correspond to weighted sampling with replacement. The k-min sketch might have certain weaker properties, but certain estimators can be obtained with relative ease from the k-min sketch. A bottom-k sketch can encode many corresponding k-mins sketches of the dataset. The same estimators derived via the k-min sketch can be applied to the bottom-k sketch. For example, a k-mins estimator can be used to determine a result responsive to the query. The estimator can be applied to one or more sketches in order to estimate one or more properties of a population associated with the dataset.

At activity 5300 , estimators can be determined. The estimators can be manually and/or automatically determined based upon an all-distance bottom-k sketch of the dataset. Once the bottom-k sketch (or all-distances bottom-k sketch, which can compactly encode bottom-k sketches of many neighborhoods) is computed, the bottom-k sketch can be used to estimate properties of the original dataset without actually having the original dataset (other forms of sampling a population can be used to estimate properties of the population). For example, to estimate election results, 1000 people out of the million can be sampled and statistics of the sample can be determined and/or used to estimate the results of the actual population. In certain exemplary embodiments, confidence intervals and/or confidence bounds can be determined.

The estimator can be based upon computed adjusted weights of an all-distance bottom-k sketch of the dataset. As used herein, the phrase based upon means determined in consideration of and/or derived from. The adjusted weights can be unbiased. The estimators of the all-distance bottom-k sketch can be obtained automatically from corresponding determined estimators of the k-min sketch of the dataset. The estimators can have exponentially distributed ranks.

In certain exemplary embodiments, adjusted weights can be automatically computed via a rank conditioning method. As used herein, the phrase rank conditioning method means an algorithm that assigns adjusted weights to items included in a bottom-k sketch of a dataset. The rank conditioning method can be adapted to determine a rank conditioning estimator. The rank conditioning estimator can have zero covariances between different records of the dataset. The adjusted weights are used for estimating the weight of subpopulations of the original dataset. The adjusted weights can be applied to items comprised in a bottom-k sketch. The adjusted weights can be adapted to be used to estimate a size of subpopulations of items. As used herein, the phrase adapted to means suitable, fit, and/or capable of performing a specified function. The bottom-k sketch can be derived from the all-distance bottom-k sketch. The weight of the dataset can be automatically calculated. The automatic estimation of properties of the dataset can be based upon the weight. Certain exemplary can, for an input selection predicate of a subpopulation, calculating an estimate on the selectivity of the sub-population. The selectivity can be one of the estimators. The selectivity can be based upon the computed adjusted weights.

Certain exemplary embodiments can be adapted to automatically compute an adjusted weight via a subset-conditioning method. The estimator of properties of the dataset can be based upon the adjusted weight. The subset-conditioning method can be adapted to compute a subset conditioning estimator. The subset conditioning estimator can have negative covariances between different records of the dataset. Certain exemplary embodiments can be adapted to, via a Markov-chain based method, compute an adjusted weight for items comprised in the all-distance bottom-k sketch. The all-distance bottom-k sketch can have exponentially distributed ranks and/or a known total weight. The estimator of properties of the dataset can be based upon the adjusted weight. A Jaccard similarity of two subsets can be automatically estimated based on an application of estimators to a bottom-k sketch of a union of the two subsets. The estimator of properties of the dataset can be based upon the resemblance.

Certain exemplary embodiments can be adapted to automatically calculate a variance of the dataset. The estimator of properties can be based upon the variance. The estimators can comprise a Horvitz-Thompson estimator. As used herein, the phrase Horvitz-Thompson estimator means an unbiased parameter of a population total of a finite population, applicable in a general case where individuals are sampled with unequal probabilities.

Certain exemplary embodiments can be adapted to, based upon an all-distance bottom-k sketch of a predetermined subset of goods, automatically render an estimated cost to market the predetermined subset of goods to a predetermined subset of consumers. As used herein, the phrase render means to display, annunciate, speak, print, and/or otherwise make perceptible to a human, for example as data, commands, text, graphics, audio, video, animation, and/or hyperlinks, etc., such as via any visual, audio, and/or haptic mechanism, such as via a display, monitor, printer, electric paper, ocular implant, cochlear implant, speaker, etc. As used herein, the phrase goods means items that are purchased and/or sold. As used herein, the phrase consumer means a potential and/or actual purchaser of goods and/or services. The predetermined subset of goods can be one of a plurality of subsets of a set of goods. The predetermined subset of consumers can be one of a plurality of subsets of a set of consumers. Estimators of the all-distance bottom-k sketch can be obtained automatically from corresponding determined estimators of the k-min sketch of the dataset.

Certain exemplary embodiments can be adapted to, based upon an all-distance bottom-k sketch of a first dataset and an all-distance bottom-k sketch of a second dataset, automatically render an estimate of a size of a planned dataset to be stored on a memory device. As used herein, the phrase plan means to make prior arrangements for. The planned dataset can be a union of the first dataset and the second dataset. Estimators of the all-distance bottom-k sketch can be obtained automatically from corresponding determined estimators of a k-min sketch of the dataset.

Certain exemplary embodiments can be adapted to automatically prompt a network user to modify a network responsive to an automatic estimation of properties of a dataset of flows through the network. As used herein, the phrase responsive means reacting to an influence and/or impetus. As used herein, the phrase prompt means to advise and/or remind. The automatic estimation can be based upon an all-distance bottom-k sketch of the dataset. The properties can comprise automatically calculated confidence intervals of subpopulation-size estimators for the all-distance bottom-k sketch. Each of the confidence intervals can be associated with a corresponding application type flowing through the network. An upper bound and a lower bound of each confidence interval can be based upon an expectation of a sum of independent Poisson trials. As used herein, the phrase independent Poisson trials means a set of discrete tests that have a covariance of approximately zero and are distributed according to a probability distribution defined by the equation

p ⁡ ( k ; λ ) = λ k ⁢ ⅇ - λ k ! ,

where k is a non-negative integer and λ is an expected count of occurrences in an interval.

Certain exemplary embodiments can be adapted to, based upon the computed adjusted weights, answering a subpopulation weight query of the dataset. Certain exemplary embodiments can be adapted to automatically determine a total weight of the bottom-k sketch.

Certain exemplary embodiments can automatically estimate properties of flows through a router. The properties can be based upon computed adjusted weights of an all-distance bottom-k sketch of the flows. The adjusted weights can be computed via a Markov-chain based method. The adjusted weights can be applied to items comprised in a bottom-k sketch. The adjusted weights can be adapted to be used to estimate a size of subpopulations of items of the flows. The bottom-k sketch can be derived from the all-distance bottom-k sketch.

In certain exemplary embodiments, a set or subset of activities 5100 - 5400 can be performed iteratively and/or repeatedly. Certain exemplary embodiments can average N estimates.

At activity 5400 , estimators can be applied. In certain exemplary embodiments, estimators determined for the k-min sketch can be applied to a bottom-k sketch and/or an all-distance bottom-k sketch. In certain exemplary embodiments, subpopulation queries can be made. For example, a sample of people, subpopulation can comprise information regarding gender, zipcode, racial and/or background, etc. Certain information can overlap. A predicate can specify a subpopulation. The predicate can be applied to the sample and/or an estimate derived therefrom. Certain exemplary embodiments can provide confidence bounds, which for a given confidence level can provide an upper bound and/or a lower bound of an estimated value. Queries can be processed from the sketch without utilizing the original dataset. Queries can be used for automatic tracking and/or mining of the dataset.

At activity 5500 , results obtained responsive to the query can be output. For example, an average of estimators and/or confidence intervals associated with the query can be outputted and/or rendered to a user.

FIG. 5 is a block diagram of an exemplary embodiment of an information device 5000 , which in certain operative embodiments can comprise, for example, server 3300 and information device 3100 , of FIG. 3 . Information device 5000 can comprise any of numerous circuits and/or components, such as for example, one or more network interfaces 5100 , one or more processors 5200 , one or more memories 5300 containing instructions 5400 , one or more input/output (I/O) devices 5500 , and/or one or more user interfaces 5600 coupled to I/O device 5500 , etc. As used herein, the phrase network interface means any physical and/or logical device, system, and/or process capable of coupling an information device to a network. Exemplary network interfaces comprise a telephone, cellular phone, cellular modem, telephone data modem, fax modem, wireless transceiver, Ethernet card, cable modem, digital subscriber line interface, bridge, hub, router, or other similar device, software to manage such a device, and/or software to provide a function of such a device.

In certain exemplary embodiments, via one or more user interfaces 5600 , such as a graphical user interface, a user can view a rendering of information related to researching, designing, modeling, creating, developing, building, manufacturing, operating, maintaining, storing, marketing, selling, delivering, selecting, specifying, requesting, ordering, receiving, returning, rating, and/or recommending any of the products, services, methods, and/or information described herein. As used herein, the phrase request means (v.) to express a need and/or desire for; to inquire and/or ask for; (n.) that which communicates an expression of desire and/or that which is asked for. As used herein, the phrase create means to make, form, produce, generate, bring into being, and/or cause to exist.

As used herein, the phrase processor means a hardware, firmware, and/or software machine and/or virtual machine comprising a set of machine-readable instructions adaptable to perform a specific task. A processor can utilize mechanical, pneumatic, hydraulic, electrical, magnetic, optical, informational, chemical, and/or biological principles, mechanisms, signals, and/or inputs to perform the task(s). In certain embodiments, a processor can act upon information by manipulating, analyzing, modifying, and/or converting it, transmitting the information for use by an executable procedure and/or an information device, and/or routing the information to an output device. A processor can function as a central processing unit, local controller, remote controller, parallel controller, and/or distributed controller, etc. Unless stated otherwise, the processor can be a general-purpose device, such as a microcontroller and/or a microprocessor, such the Pentium IV series of microprocessor manufactured by the Intel Corporation of Santa Clara, Calif. In certain embodiments, the processor can be dedicated purpose device, such as an Application Specific Integrated Circuit (ASIC) or a Field Programmable Gate Array (FPGA) that has been designed to implement in its hardware and/or firmware at least a part of an embodiment disclosed herein. A processor can reside on and use the capabilities of a controller.

Certain terms that are used substantively herein are accompanied by definitions. These terms and definitions are presented without prejudice, and, consistent with the application, the right to redefine these terms during the prosecution of this application or any application claiming priority hereto is reserved. For the purpose of interpreting a claim of any patent that claims priority hereto, each definition (or redefined term if an original definition was amended during the prosecution of that patent), functions as a clear and unambiguous disavowal of the subject matter outside of that definition.

As used herein, the phrase information device means any device on which resides a finite state machine capable of implementing at least a portion of a method, structure, and/or or graphical user interface described herein. An information device can comprise well-known communicatively coupled components, such as one or more network interfaces, one or more processors, one or more memories containing instructions, one or more input/output (I/O) devices, and/or one or more user interfaces (e.g., coupled to an I/O device) via which information can be rendered to implement one or more functions described herein. For example, an information device can be any general purpose and/or special purpose computer, such as a personal computer, video game system (e.g., PlayStation, Nintendo Gameboy, X-Box, etc.), workstation, server, minicomputer, mainframe, supercomputer, computer terminal, laptop, wearable computer, and/or Personal Digital Assistant (PDA), iPod, mobile terminal, Bluetooth device, communicator, “smart” phone (such as a Treo-like device), messaging service (e.g., Blackberry) receiver, pager, facsimile, cellular telephone, a traditional telephone, telephonic device, a programmed microprocessor or microcontroller and/or peripheral integrated circuit elements, a digital signal processor, an ASIC or other integrated circuit, a hardware electronic logic circuit such as a discrete element circuit, and/or a programmable logic device such as a PLD, PLA, FPGA, or PAL, or the like, etc.

As used herein, the phrase input/output (I/O) device means any sensory-oriented input and/or output device, such as an audio, visual, haptic, olfactory, and/or taste-oriented device, including, for example, a monitor, display, projector, overhead display, keyboard, keypad, mouse, trackball, joystick, gamepad, wheel, touchpad, touch panel, pointing device, microphone, speaker, video camera, camera, scanner, printer, haptic device, vibrator, tactile simulator, and/or tactile pad, potentially including a port to which an I/O device can be attached or connected. As used herein, the phrase port means a data connection in an information device and/or networking device to which a peripheral device or a transmission line from a remote terminal and/or remote system can be attached. As used herein, the phrase system means a collection of mechanisms, devices, machines, articles of manufacture, processes, data, and/or instructions, the collection designed to perform one or more specific functions.

As used herein, the phrase haptic means involving the human sense of kinesthetic movement and/or the human sense of touch. Among the many potential haptic experiences are numerous sensations, body-positional differences in sensations, and time-based changes in sensations that are perceived at least partially in non-visual, non-audible, and non-olfactory manners, including the experiences of tactile touch (being touched), active touch, grasping, pressure, friction, fraction, slip, stretch, force, torque, impact, puncture, vibration, motion, acceleration, jerk, pulse, orientation, limb position, gravity, texture, gap, recess, viscosity, pain, itch, moisture, temperature, thermal conductivity, and thermal capacity.

As used herein, the phrase said means when used in a system or device claim, an article indicating a subsequent claim term that has been previously introduced. As used herein, the phrase substantially means to a considerable, large, and/or great, but not necessarily whole and/or entire, extent and/or degree. As used herein, the phrase user means a person, organization, process, device, program, protocol, and/or system that uses a device, system, process, and/or service.

As used herein, the phrase user interface means a device and/or software program for rendering information to a user and/or requesting information from the user. A user interface can include at least one of textual, graphical, audio, video, animation, and/or haptic elements. A textual element can be provided, for example, by a printer, monitor, display, projector, etc. A graphical element can be provided, for example, via a monitor, display, projector, and/or visual indication device, such as a light, flag, beacon, etc. An audio element can be provided, for example, via a speaker, microphone, and/or other sound generating and/or receiving device. A video element or animation element can be provided, for example, via a monitor, display, projector, and/or other visual device. A haptic element can be provided, for example, via a very low frequency speaker, vibrator, tactile stimulator, tactile pad, simulator, keyboard, keypad, mouse, trackball, joystick, gamepad, wheel, touchpad, touch panel, pointing device, and/or other haptic device, etc. A user interface can include one or more textual elements such as, for example, one or more letters, number, symbols, etc. A user interface can include one or more graphical elements such as, for example, an image, photograph, drawing, icon, window, title bar, panel, sheet, tab, drawer, matrix, table, form, calendar, outline view, frame, dialog box, static text, text box, list, pick list, pop-up list, pull-down list, menu, tool bar, dock, check box, radio button, hyperlink, browser, button, control, palette, preview panel, color wheel, dial, slider, scroll bar, cursor, status bar, stepper, and/or progress indicator, etc. A textual and/or graphical element can be used for selecting, programming, adjusting, changing, specifying, etc. an appearance, background color, background style, border style, border thickness, foreground color, font, font style, font size, alignment, line spacing, indent, maximum data length, validation, query, cursor type, pointer type, autosizing, position, and/or dimension, etc. A user interface can include one or more audio elements such as, for example, a volume control, pitch control, speed control, voice selector, and/or one or more elements for controlling audio play, speed, pause, fast forward, reverse, etc. A user interface can include one or more video elements such as, for example, elements controlling video play, speed, pause, fast forward, reverse, zoom-in, zoom-out, rotate, and/or tilt, etc. A user interface can include one or more animation elements such as, for example, elements controlling animation play, pause, fast forward, reverse, zoom-in, zoom-out, rotate, tilt, color, intensity, speed, frequency, appearance, etc. A user interface can include one or more haptic elements such as, for example, elements utilizing tactile stimulus, force, pressure, vibration, motion, displacement, temperature, etc.

Note

Still other substantially and specifically practical and useful embodiments will become readily apparent to those skilled in this art from reading the above-recited and/or herein-included detailed description and/or drawings of certain exemplary embodiments. It should be understood that numerous variations, modifications, and additional embodiments are possible, and accordingly, all such variations, modifications, and embodiments are to be regarded as being within the scope of this application.

Thus, regardless of the content of any portion (e.g., title, field, background, summary, description, abstract, drawing figure, etc.) of this application, unless clearly specified to the contrary, such as via explicit definition, assertion, or argument, with respect to any claim, whether of this application and/or any claim of any application claiming priority hereto, and whether originally presented or otherwise:

there is no requirement for the inclusion of any particular described or illustrated characteristic, function, activity, or element, any particular sequence of activities, or any particular interrelationship of elements; any elements can be integrated, segregated, and/or duplicated; any activity can be repeated, any activity can be performed by multiple entities, and/or any activity can be performed in multiple jurisdictions; and any activity or element can be specifically excluded, the sequence of activities can vary, and/or the interrelationship of elements can vary.

Moreover, when any number or range is described herein, unless clearly stated otherwise, that number or range is approximate. When any range is described herein, unless clearly stated otherwise, that range includes all values therein and all subranges therein. For example, if a range of 1 to 10 is described, that range includes all values therebetween, such as for example, 1.1, 2.5, 3.335, 5, 6.179, 8.9999, etc., and includes all subranges therebetween, such as for example, 1 to 3.65, 2.8 to 8.14, 1.93 to 9, etc.

When any claim element is followed by a drawing element number, that drawing element number is exemplary and non-limiting on claim scope.

Any information in any material (e.g., a United States patent, United States patent application, book, article, etc.) that has been incorporated by reference herein, is only incorporated by reference to the extent that no conflict exists between such information and the other statements and drawings set forth herein. In the event of such conflict, including a conflict that would render invalid any claim herein or seeking priority hereto, then any such conflicting information in such material is specifically not incorporated by reference herein.

Accordingly, every portion (e.g., title, field, background, summary, description, abstract, drawing figure, etc.) of this application, other than the claims themselves, is to be regarded as illustrative in nature, and not as restrictive.