waashk/dblp huggingface dataset:
kddcs: a load-balanced in-network data-centric storage scheme for sensor networks. we propose an in-network data-centric storage (indcs) scheme for answering ad-hoc queries in sensor networks. previously proposed in-network storage (ins) schemes suffered from storage hot-spots that are formed if either the sensors' locations are not uniformly distributed over the coverage area, or the distribution of sensor readings is not uniform over the range of possible reading values. our k-d tree based data-centric storage (kddcs) scheme maintains the invariant that the storage of events is distributed reasonably uniformly among the sensors. kddcs is composed of a set of distributed algorithms whose running time is within a poly-log factor of the diameter of the network. the number of messages any sensor has to send, as well as the bits in those messages, is poly-logarithmic in the number of sensors. load balancing in kddcs is based on defining and distributively solving a theoretical problem that we call the weighted split median problem. in addition to analytical bounds on kddcs individual algorithms, we provide experimental evidence of our scheme's general efficiency, as well as its ability to avoid the formation of storage hot-spots of various sizes, unlike all previous indcs schemes.
effective and efficient similarity search in time series. we present dsa - derivative time series segment approximation, a novel representation model for time series designed for effective and efficient similarity search. dsa substantially exploits derivative estimation, segmentation and dimensionality reduction to meet at least the requirements of high sensitivity to main features (trends) of time series and robustness to outliers. experiments show that dsa is drastically faster and still as good or better than the prominent state-of-the-art similarity methods.
effective and efficient classification on a search-engine model. traditional document classification frameworks, which apply the learned classifier to each document in a corpus one by one, are infeasible for extremely large document corpora, like the web or large corporate intranets. we consider the classification problem on a corpus that has been processed primarily for the purpose of searching, and thus our access to documents is solely through the inverted index of a large scale search engine. our main goal is to build the "best" short query that characterizes a document class using operators normally available within large engines. we show that surprisingly good classification accuracy can be achieved on average over multiple classes by queries with as few as 10 terms. moreover, we show that optimizing the efficiency of query execution by careful selection of these terms can further reduce the query costs. more precisely, we show that on our set-up the best 10 terms query canachieve 90% of the accuracy of the best svm classifier (14000 terms), and if we are willing to tolerate a reduction to 86% of the best svm, we can build a 10 terms query that can be executed more than twice as fast as the best 10 terms query.
resource-aware kernel density estimators over streaming data. a fundamental building block of many data mining and analysis approaches is density estimation as it provides a comprehensive statistical model of a data distribution. for that reason, its application to transient data streams is highly desirable. a convenient, nonparametric method for density estimation utilizes kernels. however, its computational complexity collides with the rigid processing requirements of data streams. in this work, we present a new approach to this problem that combines linear processing cost with a constant amount of allocated memory. our approach also supports a dynamic memory adaptation to changing system resources.
a neighborhood-based approach for clustering of linked document collections. this paper addresses the problem of automatically structuring linked document collections by using clustering. in contrast to traditional clustering, we study the clustering problem in the light of available link structure information for the data set (e.g., hyperlinks among web documents or co-authorship among bibliographic data entries). our approach is based on iterative relaxation of cluster assignments, and can be built on top of any clustering algorithm. this technique results in higher cluster purity, better overall accuracy, and make self-organization more robust.
continuous keyword search on multiple text streams. in this paper we address the issue of continuous keyword queries on multiple textual streams. this line of work represents a significant departure from previous keyword search models that assumed a static database. in our model the user poses a query comprised by a collection of keywords, which is subsequently applied on multiple text streams (these can be rss news feeds, tv closed captions, emails, etc). a result to a query is a combination of streams "sufficiently correlated" to each other that collectively contain all query keywords within a specified time span.
3dstring: a feature string kernel for 3d object classification on voxelized data. classification of 3d objects remains an important task in many areas of data management such as engineering, medicine or biology. as a common preprocessing step in current approaches to classification of voxelized 3d objects, voxel representations are transformed into a feature vector description.in this article, we introduce an approach of transforming 3d objects into feature strings which represent the distribution of voxels over the voxel grid. attractively, this feature string extraction can be performed in linear runtime with respect to the number of voxels. we define a similarity measure on these feature strings that counts common k-mers in two input strings, which is referred to as the spectrum kernel in the field of kernel methods. we prove that on our feature strings, this similarity measure can be computed in time linear to the number of different characters in these strings. this linear runtime behavior makes our kernel attractive even for large datasets that occur in many application domains. furthermore, we explain that our similarity measure induces a metric which allows to combine it with an m-tree for handling of large volumes of data. classification experiments on two published benchmark datasets show that our novel approach is competitive with the best state-of-the-art methods for 3d object classification.
integration of cluster ensemble and em based text mining for microarray gene cluster identification and annotation. in this paper, we design and develop a unified system ge-miner (gene expression miner) to integrate cluster ensemble, text clustering and multi document summarization and provide an environment for comprehensive gene expression data analysis. we present a novel cluster ensemble approach to generate high quality gene cluster. in our text summarization module, given a gene cluster, our expectation maximization (em) based algorithm can automatically identify subtopics and extract most probable terms for each topic. then, the extracted top k topical terms from each subtopic are combined to form the biological explanation of each gene cluster. experimental results demonstrate that our system can obtain high quality clusters and provide informative key terms for the gene clusters.
adaptive non-linear clustering in data streams. data stream clustering has emerged as a challenging and interesting problem over the past few years. due to the evolving nature, and one-pass restriction imposed by the data stream model, traditional clustering algorithms are inapplicable for stream clustering. this problem becomes even more challenging when the data is high-dimensional and the clusters are not linearly separable in the input space. in this paper, we propose a nonlinear stream clustering algorithm that adapts to the stream's evolutionary changes. using the kernel methods for dealing with the non-linearity of data separation, we propose a novel 2-tier stream clustering architecture. tier-1 captures the temporal locality in the stream, by partitioning it into segments, using a kernel-based novelty detection approach. tier-2 exploits this segment structure to continuously project the streaming data nonlinearly onto a low-dimensional space (lds), before assigning them to a cluster. we demonstrate the effectiveness of our approach through extensive experimental evaluation on various real-world datasets.
regularized locality preserving indexing via spectral regression. we consider the problem of document indexing and representation. recently, locality preserving indexing (lpi) was proposed for learning a compact document subspace. different from latent semantic indexing (lsi) which is optimal in the sense of global euclidean structure, lpi is optimal in the sense of local manifold structure. however, lpi is not efficient in time and memory which makes it difficult to be applied to very large data set. specifically, the computation of lpi involves eigen-decompositions of two dense matrices which is expensive. in this paper, we propose a new algorithm called regularized locality preserving indexing (rlpi). benefit from recent progresses on spectral graph analysis, we cast the original lpi algorithm into a regression framework which enable us to avoid eigen-decomposition of dense matrices. also, with the regression based framework, different kinds of regularizers can be naturally incorporated into our algorithm which makes it more flexible. extensive experimental results show that rlpi obtains similar or better results comparing to lpi and it is significantly faster, which makes it an efficient and effective data preprocessing method for large scale text clustering, classification and retrieval.
cp/cv: concept similarity mining without frequency information from domain describing taxonomies. domain specific ontologies are heavily used in many applications. for instance, these form the bases on which similarity/dissimilarity between keywords are extracted for various knowledge discovery and retrieval tasks. existing similarity computation schemes can be categorized as (a) structure- or (b) information-based approaches. structure based approaches compute dissimilarity between keywords using a (weighted) count of edges between two keywords. information-base approaches, on the other hand, leverage available corpora to extract additional information, such as keyword frequency, to achieve better performance in similarity computation than structure-based approaches. unfortunately, in many application domains (such as applications that rely on unique-keys in a relational database), frequency information required by information-based approaches does not exist. in this paper, we note that there is a third way of computing similarity: if each node in a given hierarchy can be represented as a vector of related concepts, these vectors could be compared to compute similarities. this requires mapping concept-nodes in a given hierarchy onto a concept space. in this paper, we propose a concept propagation (cp) scheme, which relies on the semantical relationships between concepts implied by the structure of the hierarchy to annotate each concept-node with a concept-vector (cv). we refer to this approach as cp/cv. comparison of keyword similarity results shows that cp/cv provides significantly better (upto 33%) results than existing structure-based schemes. also, even if cp/cv does not assume the availability of an appropriate corpus to extract keyword frequency information, our approach matches (and slightly improves on) the performance of information-based approaches.
secure search in enterprise webs: tradeoffs in efficient implementation for document level security. document level security (dls) -- enforcing permissions prevailing at the time of search -- is specified as a mandatory requirement in many enterprise search applications. unfortunately, depending upon implementation details and values of key parameters, dls may come at a high price in increased query processing time, leading to an unacceptably slow search experience. in this paper we present a model and a method for carrying out secure search in the presence of dls within enterprise webs. we report on two alternative commercial dls search implementations. using a 10,000 document experimental dls environment, we graph the dependence of query processing time on result set size and visibility density for different classes of user. scaled up to collections of tens of thousands of documents, our results suggest that query times will be unacceptable if exact counts of matching documents are required and also for users who can view only a small proportion of documents. we show that the time to conduct access checks is dramatically increased if requests must be sent off-server, even on a local network, and discuss methods for reducing the cost of security checks. we conclude that enterprises can effectively reduce dls overheads by organizing documents in such a way that most access checking can be at collection rather than document level, by forgoing accurate match counts, by using caching, batching or hierarchical methods to cut costs of dls checking and, if applicable, by using a single portal both to access and search documents.
a data stream language and system designed for power and extensibility. by providing an integrated and optimized support for user-defined aggregates (udas), data stream management systems (dsms) can achieve superior power and generality while preserving compatibility with current sql standards. this is demonstrated by the stream mill system that, through is expressive stream language (esl), efficiently supports a wide range of applications - including very advanced ones such as data stream mining, streaming xml processing, time-series queries, and rfid event processing. esl supports physical and logical windows (with optional slides and tumbles) on both built-in aggregates and udas, using a simple framework that applies uniformly to both aggregate functions written in an external procedural languages and those natively written in esl. the constructs introduced in esl extend the power and generality of dsms, and are conducive to uda-specific optimization and efficient execution as demonstrated by several experiments.
estimation, sensitivity, and generalization in parameterized retrieval models. in this work we investigate three important aspects of parameterized retrieval models: estimation, sensitivity, and generalization. since all parameterized models, even those based on heuristics, have inherent uncertainty, we study these issues using statistical tools.
maximizing the sustained throughput of distributed continuous queries. monitoring systems today often involve continuous queries over streaming data, in a distributed collaborative system. the distribution of query operators over a network of processors, and their processing sequence, form a query configuration with inherent constraints on the throughput it can support. in this paper we propose to optimize stream queries with respect to a version of throughput measure, the profiled input throughput. this measure is focused on matching the expected behavior of the input streams. to prune the search space we used hill-climbing techniques that proved to be efficient and effective.
capturing community search expertise for personalized web search using snippet-indexes. we describe and evaluate an approach to capturing and re-using search expertise within a community of like minded searchers, such as the employees of a company or organisation. within knowledge based industries, search expertise - the ability to quickly and accurately locate information according to a specific information need - is an important corporate asset and in our approach we attempt to capture this knowledge by mining the title and snippet texts of results that have been selected by community members in response to their queries. our assumption is that the snippet text of a result must play a role in helping users to judge the initial relevance of that result and that the snippet terms of selected results must contain especially informative terms about the goals and preferences of the searchers. in other words, results are selected because the user recognises certain combinations of terms in their snippets which are related to their information needs. our approach seeks to build a community-based snippet index that reflects the evolving interests of a group of searchers. this index is then used to re-rank the results returned by some underlying search engine by boosting the ranking of key results that have been frequently selected for similar queries by community members in the past.
ir principles for content-based indexing and retrieval of functional brain images. in this paper, we explore the concept of a "library of brain images", which implies not only a repository of brain images, but also efficient search and retrieval mechanisms that are based on models derived from ir practice. as a preliminary study, we have worked with a collection of functional mri brain images assembled in the study of several distinct cognitive tasks. we adapt several classical ir methods (inverted indexing, tfidf and latent semantic indexing(lsi)) to content-based brain image retrieval. our results show that efficient and accurate retrieval of brain images is possible, and that representations motivated by the ir perspective are somewhat more effective than are methods based on retaining the full image information.
estimating corpus size via queries. we consider the problem of estimating the size of a collection of documents using only a standard query interface. our main idea is to construct an unbiased and low-variance estimator that can closely approximate the size of any set of documents defined by certain conditions, including that each document in the set must match at least one query from a uniformly sampleable query pool of known size, fixed in advance.using this basic estimator, we propose two approaches to estimating corpus size. the first approach requires a uniform random sample of documents from the corpus. the second approach avoids this notoriously difficult sample generation problem, and instead uses two fairly uncorrelated sets of terms as query pools; the accuracy of the second approach depends on the degree of correlation among the two sets of terms.experiments on a large trec collection and on three major search engines demonstrates the effectiveness of our algorithms.
a document-centric approach to static index pruning in text retrieval systems. we present a static index pruning method, to be used in ad-hoc document retrieval tasks, that follows a document-centric approach to decide whether a posting for a given term should remain in the index or not. the decision is made based on the term's contribution to the document's kullback-leibler divergence from the text collection's global language model. our technique can be used to decrease the size of the index by over 90%, at only a minor decrease in retrieval effectiveness. it thus allows us to make the index small enough to fit entirely into the main memory of a single pc, even for large text collections containing millions of documents. this results in great efficiency gains, superior to those of earlier pruning methods, and an average response time around 20 ms on the gov2 document collection.
computing block importance for searching on web sites. in this paper we consider the problem of using the block structure of a web page to improve ranking results when searching for information on web sites. given the block structure of the web pages as input, we propose a method for computing the importance of each block (in the form of block weights) in a web collection. as we show through experiments, the deployment of our method may allow a significant improvement in the quality of search results. we ran experiments to compare the quality of search results when using our method to the quality obtained when using no structure information. when compared to a ranking method that considered pages as monolithic units, our block-based ranking method led to improvements in the quality of search results in experiments with two sites with heterogeneous structures. further, our method does not increase the cost of processing queries when compared to the systems using no structural information.
constructing better document and query models with markov chains. document and query expansions have been used separately in previous studies to enhance the representation of documents and queries. in this paper, we propose a general method that integrates both of them. expansion is carried out using multi-stage markov chains. our experiments show that this method significantly outperforms the existing approaches.
learning to join everything. text, speech, images, video, dna sequences provide information about entities that people can recognize when looking at a particular instance. but those entities and their attributes and relationships are not directly accessible to queries that join across types of sources. information extraction methods based on supervised machine learning recognize mentions of entities and relationships of predefined types in different kinds of sources, which can then be used to answer some useful types of queries. however, supervised learning relies on hand-annotated training sets that are difficult to create and limit what types of entities and relationships can be joined for new applications. these limitations have prompted research into unsupervised extraction methods that rely on correlations among sources rather than hand-annotated training sets. while these methods are not yet as accurate as those based on supervised learning, they have the potential for a new query-by-example approach to information integration in which seed sets of query answers are expanded into ranked lists of potential answers by learning occurrence patterns from the seed answers. i will give examples of both types of methods from our research on biomedical information extraction, leading to some ideas on a possible convergence of search and databases through machine learning.
efficient join processing over uncertain data. in many applications data values are inherently uncertain. this includes moving-objects, sensors and biological databases. there has been recent interest in the development of database management systems that can handle uncertain data. some proposals for such systems include attribute values that are uncertain. in particular, an attribute value can be modeled as a range of possible values, associated with a probability density function. previous efforts for this type of data have only addressed simple queries such as range and nearest-neighbor queries. queries that join multiple relations have not been addressed in earlier work despite the significance of joins in databases. in this paper we address join queries over uncertain data. we propose a semantics for the join operation, define probabilistic operators over uncertain data, and propose join algorithms that provide efficient execution of probabilistic joins. the paper focuses on an important class of joins termed probabilistic threshold joins that avoid some of the semantic complexities of dealing with uncertain data. for this class of joins we develop three sets of optimization techniques: item-level, page-level, and index-level pruning. these techniques facilitate pruning with little space and time overhead, and are easily adapted to most join algorithms. we verify the performance of these techniques experimentally.