OpenRaiser/Intern-Atlas huggingface dataset:
Boosting XML Filtering with a Scalable FPGA-based Architecture
Venue: arXiv cs.AR 2009
Year: 2009

The growing amount of XML encoded data exchanged over the Internet increases the importance of XML based publish-subscribe (pub-sub) and content based routing systems. The input in such systems typically consists of a stream of XML documents and a set of user subscriptions expressed as XML queries. The pub-sub system then filters the published documents and passes them to the subscribers. Pub-sub systems are characterized by very high input ratios, therefore the processing time is critical. In this paper we propose a "pure hardware" based solution, which utilizes XPath query blocks on FPGA to solve the filtering problem. By utilizing the high throughput that an FPGA provides for parallel processing, our approach achieves drastically better throughput than the existing software or mixed (hardware/software) architectures. The XPath queries (subscriptions) are translated to regular expressions which are then mapped to FPGA devices. By introducing stacks within the FPGA we are able to express and process a wide range of path queries very efficiently, on a scalable environment. Moreover, the fact that the parser and the filter processing are performed on the same FPGA chip, eliminates expensive communication costs (that a multi-core system would need) thus enabling very fast and efficient pipelining. Our experimental evaluation reveals more than one order of magnitude improvement compared to traditional pub/sub systems.
Principles for Inconsistency
Venue: arXiv cs.DB 2009
Year: 2009

Data consistency is very desirable because strong semantic properties make it easier to write correct programs that perform as users expect. However, there are good reasons why consistency may have to be weakened to achieve other business goals. In this CIDR 2009 Perspectives paper, we present real-world reasons inconsistency may be necessary, offer principles for managing inconsistency coherently, and describe implementation approaches we are investigating for sustainably scalable systems that offer comprehensible user experiences despite inconsistency.
Greedy Gossip with Eavesdropping
Venue: arXiv cs.DC 2009
Year: 2009

This paper presents greedy gossip with eavesdropping (GGE), a novel randomized gossip algorithm for distributed computation of the average consensus problem. In gossip algorithms, nodes in the network randomly communicate with their neighbors and exchange information iteratively. The algorithms are simple and decentralized, making them attractive for wireless network applications. In general, gossip algorithms are robust to unreliable wireless conditions and time varying network topologies. In this paper we introduce GGE and demonstrate that greedy updates lead to rapid convergence. We do not require nodes to have any location information. Instead, greedy updates are made possible by exploiting the broadcast nature of wireless communications. During the operation of GGE, when a node decides to gossip, instead of choosing one of its neighbors at random, it makes a greedy selection, choosing the node which has the value most different from its own. In order to make this selection, nodes need to know their neighbors' values. Therefore, we assume that all transmissions are wireless broadcasts and nodes keep track of their neighbors' values by eavesdropping on their communications. We show that the convergence of GGE is guaranteed for connected network topologies. We also study the rates of convergence and illustrate, through theoretical bounds and numerical simulations, that GGE consistently outperforms randomized gossip and performs comparably to geographic gossip on moderate-sized random geometric graph topologies.
Business in the Grid
Venue: arXiv cs.DC 2009
Year: 2009

From 2004 to 2007 the Business In the Grid (BIG) project took place and was driven by the following goals: Firstly, make business aware of Grid technology and, secondly, try to explore new business models. We disseminated Grid computing by mainly concentrating on the central European market and interviewed several companies in order to gain insights into the Grid acceptance in industrial environments. In this article we present the results of the project, elaborate on a critical discussion on business adaptations, and describe a novel dynamic authorization workflow for business processes in the Grid.
SocialScope: Enabling Information Discovery on Social Content Sites
Venue: arXiv cs.DB 2009
Year: 2009

Recently, many content sites have started encouraging their users to engage in social activities such as adding buddies on Yahoo! Travel and sharing articles with their friends on New York Times. This has led to the emergence of {\em social content sites}, which is being facilitated by initiatives like OpenID (http://www.openid.net/) and OpenSocial (http://www.opensocial.org/). These community standards enable the open access to users' social profiles and connections by individual content sites and are bringing content-oriented sites and social networking sites ever closer. The integration of content and social information raises new challenges for {\em information management and discovery} over such sites. We propose a logical architecture, named \kw{SocialScope}, consisting of three layers, for tackling the challenges. The {\em content management} layer is responsible for integrating, maintaining and physically accessing the content and social data. The {\em information discovery} layer takes care of analyzing content to derive interesting new information, and interpreting and processing the user's information need to identify relevant information. Finally, the {\em information presentation} layer explores the discovered information and helps users better understand it in a principled way. We describe the challenges in each layer and propose solutions for some of those challenges. In particular, we propose a uniform algebraic framework, which can be leveraged to uniformly and flexibly specify many of the information discovery and analysis tasks and provide the foundation for the optimization of those tasks.
Approximate Nearest Neighbor Search through Comparisons
Venue: arXiv cs.DS 2009
Year: 2009

This paper addresses the problem of finding the nearest neighbor (or one of the R-nearest neighbors) of a query object q in a database of n objects. In contrast with most existing approaches, we can only access the ``hidden'' space in which the objects live through a similarity oracle. The oracle, given two reference objects and a query object, returns the reference object closest to the query object. The oracle attempts to model the behavior of human users, capable of making statements about similarity, but not of assigning meaningful numerical values to distances between objects.
Reference Resolution within the Framework of Cognitive Grammar
Venue: arXiv cs.CL 2009
Year: 2009

Following the principles of Cognitive Grammar, we concentrate on a model for reference resolution that attempts to overcome the difficulties previous approaches, based on the fundamental assumption that all reference (independent on the type of the referring expression) is accomplished via access to and restructuring of domains of reference rather than by direct linkage to the entities themselves. The model accounts for entities not explicitly mentioned but understood in a discourse, and enables exploitation of discursive and perceptual context to limit the set of potential referents for a given referring expression. As the most important feature, we note that a single mechanism is required to handle what are typically treated as diverse phenomena. Our approach, then, provides a fresh perspective on the relations between Cognitive Grammar and the problem of reference.
Singularity of Sparse Circulant Matrices is NP-complete
Venue: arXiv cs.CC 2009
Year: 2009

It is shown by Karp reduction that deciding the singularity of $(2^n - 1) \times (2^n - 1)$ sparse circulant matrices (SC problem) is NP-complete. We can write them only implicitly, by indicating values of the $2 + n(n + 1)/2$ eventually nonzero entries of the first row and can make all matrix operations with them. The positions are $0, 1, 2^{i} + 2^{j}$. The complexity parameter is $n$. Mulmuley's work on the rank of matrices \cite{Mulmuley87} makes SC stand alone in a list of 3,000 and growing NP-complete problems.
Memory Consistency Conditions for Self-Assembly Programming
Venue: arXiv cs.DS 2009
Year: 2009

Perhaps the two most significant theoretical questions about the programming of self-assembling agents are: (1) necessary and sufficient conditions to produce a unique terminal assembly, and (2) error correction. We address both questions, by reducing two well-studied models of tile assembly to models of distributed shared memory (DSM), in order to obtain results from the memory consistency systems induced by tile assembly systems when simulated in the DSM setting. The Abstract Tile Assembly Model (aTAM) can be simulated by a DSM system that obeys causal consistency, and the locally deterministic tile assembly systems in the aTAM correspond exactly to the concurrent-write free programs that simulate tile assembly in such a model. Thus, the detection of the failure of local determinism (which had formerly been an open problem) reduces to the detection of data races in simulating programs. Further, the Kinetic Tile Assembly Model can be simulated by a DSM system that obeys GWO, a memory consistency condition defined by Steinke and Nutt. (To our knowledge, this is the first natural example of a DSM system that obeys GWO, but no stronger consistency condition.) We combine these results with the observation that self-assembly algorithms are local algorithms, and there exists a fast conversion of deterministic local algorithms into deterministic self-stabilizing algorithms. This provides an "immediate" generalization of a theorem by Soloveichik et al. about the existence of tile assembly systems that simultaneously perform two forms of self-stabilization: proofreading and self-healing. Our reductions and proof techniques can be extended to the programming of self-assembling agents in a variety of media, not just DNA tiles, and not just two-dimensional surfaces.
An Optimal Labeling Scheme for Ancestry Queries
Venue: arXiv cs.DS 2009
Year: 2009

An ancestry labeling scheme assigns labels (bit strings) to the nodes of rooted trees such that ancestry queries between any two nodes in a tree can be answered merely by looking at their corresponding labels. The quality of an ancestry labeling scheme is measured by its label size, that is the maximal number of bits in a label of a tree node. In addition to its theoretical appeal, the design of efficient ancestry labeling schemes is motivated by applications in web search engines. For this purpose, even small improvements in the label size are important. In fact, the literature about this topic is interested in the exact label size rather than just its order of magnitude. As a result, following the proposal of a simple interval-based ancestry scheme with label size $2\log_2 n$ bits (Kannan et al., STOC '88), a considerable amount of work was devoted to improve the bound on the size of a label. The current state of the art upper bound is $\log_2 n + O(\sqrt{\log n})$ bits (Abiteboul et al., SODA '02) which is still far from the known $\log_2 n + Ω(\log\log n)$ bits lower bound (Alstrup et al., SODA '03). In this paper we close the gap between the known lower and upper bounds, by constructing an ancestry labeling scheme with label size $\log_2 n + O(\log\log n)$ bits. In addition to the optimal label size, our scheme assigns the labels in linear time and can support any ancestry query in constant time.
On the Symmetric Gaussian Interference Channel with Partial Unidirectional Cooperation
Venue: arXiv cs.IT 2009
Year: 2009

A two-user symmetric Gaussian Interference Channel (IC) is considered in which a noiseless unidirectional link connects one encoder to the other. Having a constant capacity, the additional link provides partial cooperation between the encoders. It is shown that the available cooperation can dramatically increase the sum-capacity of the channel. This fact is proved based on comparison of proposed lower and upper bounds on the sum-capacity. Partitioning the data into three independent messages, namely private, common, and cooperative ones, the transmission strategy used to obtain the lower bound enjoys a simple type of Han-Kobayashi scheme together with a cooperative communication scheme. A Genie-aided upper bound is developed which incorporates the capacity of the cooperative link. Other upper bounds are based on the sum-capacity of the Cognitive Radio Channel and cut-set bounds. For the strong interference regime, the achievablity scheme is simplified to employ common and/or cooperative messages but not the private one. Through a careful analysis it is shown that the gap between these bounds is at most one and two bits per real dimension for strong and weak interference regimes, respectively. Moreover, the Generalized Degrees-of-Freedom of the channel is characterized.
Electric routing and concurrent flow cutting
Venue: arXiv cs.DM 2009
Year: 2009

We investigate an oblivious routing scheme, amenable to distributed computation and resilient to graph changes, based on electrical flow. Our main technical contribution is a new rounding method which we use to obtain a bound on the L1->L1 operator norm of the inverse graph Laplacian. We show how this norm reflects both latency and congestion of electric routing.
Adaptive Spatial Intercell Interference Cancellation in Multicell Wireless Networks
Venue: arXiv cs.IT 2009
Year: 2009

Downlink spatial intercell interference cancellation (ICIC) is considered for mitigating other-cell interference using multiple transmit antennas. A principle question we explore is whether it is better to do ICIC or simply standard single-cell beamforming. We explore this question analytically and show that beamforming is preferred for all users when the edge SNR (signal-to-noise ratio) is low ($<0$ dB), and ICIC is preferred when the edge SNR is high ($>10$ dB), for example in an urban setting. At medium SNR, a proposed adaptive strategy, where multiple base stations jointly select transmission strategies based on the user location, outperforms both while requiring a lower feedback rate than the pure ICIC approach. The employed metric is sum rate, which is normally a dubious metric for cellular systems, but surprisingly we show that even with this reward function the adaptive strategy also improves fairness. When the channel information is provided by limited feedback, the impact of the induced quantization error is also investigated. It is shown that ICIC with well-designed feedback strategies still provides significant throughput gain.
Median K-flats for hybrid linear modeling with many outliers
Venue: arXiv cs.CV 2009
Year: 2009

We describe the Median K-Flats (MKF) algorithm, a simple online method for hybrid linear modeling, i.e., for approximating data by a mixture of flats. This algorithm simultaneously partitions the data into clusters while finding their corresponding best approximating l1 d-flats, so that the cumulative l1 error is minimized. The current implementation restricts d-flats to be d-dimensional linear subspaces. It requires a negligible amount of storage, and its complexity, when modeling data consisting of N points in D-dimensional Euclidean space with K d-dimensional linear subspaces, is of order O(n K d D+n d^2 D), where n is the number of iterations required for convergence (empirically on the order of 10^4). Since it is an online algorithm, data can be supplied to it incrementally and it can incrementally produce the corresponding output. The performance of the algorithm is carefully evaluated using synthetic and real data.
On the largest empty axis-parallel box amidst $n$ points
Venue: arXiv cs.CG 2009
Year: 2009

We give the first nontrivial upper and lower bounds on the maximum volume of an empty axis-parallel box inside an axis-parallel unit hypercube in $\RR^d$ containing $n$ points. For a fixed $d$, we show that the maximum volume is of the order $Θ(\frac{1}{n})$. We then use the fact that the maximum volume is $Ω(\frac{1}{n})$ in our design of the first efficient $(1-\eps)$-approximation algorithm for the following problem: Given an axis-parallel $d$-dimensional box $R$ in $\RR^d$ containing $n$ points, compute a maximum-volume empty axis-parallel $d$-dimensional box contained in $R$. The running time of our algorithm is nearly linear in $n$, for small $d$, and increases only by an $O(\log{n})$ factor when one goes up one dimension. No previous efficient exact or approximation algorithms were known for this problem for $d \geq 4$. As the problem has been recently shown to be NP-hard in arbitrary high dimensions (i.e., when $d$ is part of the input), the existence of efficient exact algorithms is unlikely. We also obtain tight estimates on the maximum volume of an empty axis-parallel hypercube inside an axis-parallel unit hypercube in $\RR^d$ containing $n$ points. For a fixed $d$, this maximum volume is of the same order order $Θ(\frac{1}{n})$. A faster $(1-\eps)$-approximation algorithm, with a milder dependence on $d$ in the running time, is obtained in this case.
An Authentication Code against Pollution Attacks in Network Coding
Venue: arXiv cs.IT 2009
Year: 2009

Systems exploiting network coding to increase their throughput suffer greatly from pollution attacks which consist of injecting malicious packets in the network. The pollution attacks are amplified by the network coding process, resulting in a greater damage than under traditional routing. In this paper, we address this issue by designing an unconditionally secure authentication code suitable for multicast network coding. The proposed scheme is robust against pollution attacks from outsiders, as well as coalitions of malicious insiders. Intermediate nodes can verify the integrity and origin of the packets received without having to decode, and thus detect and discard the malicious messages in-transit that fail the verification. This way, the pollution is canceled out before reaching the destinations. We analyze the performance of the scheme in terms of both multicast throughput and goodput, and show the goodput gains. We also discuss applications to file distribution.
On Low Distortion Embeddings of Statistical Distance Measures into Low Dimensional Spaces
Venue: arXiv cs.CG 2009
Year: 2009

Statistical distance measures have found wide applicability in information retrieval tasks that typically involve high dimensional datasets. In order to reduce the storage space and ensure efficient performance of queries, dimensionality reduction while preserving the inter-point similarity is highly desirable. In this paper, we investigate various statistical distance measures from the point of view of discovering low distortion embeddings into low-dimensional spaces. More specifically, we consider the Mahalanobis distance measure, the Bhattacharyya class of divergences and the Kullback-Leibler divergence. We present a dimensionality reduction method based on the Johnson-Lindenstrauss Lemma for the Mahalanobis measure that achieves arbitrarily low distortion. By using the Johnson-Lindenstrauss Lemma again, we further demonstrate that the Bhattacharyya distance admits dimensionality reduction with arbitrarily low additive error. We also examine the question of embeddability into metric spaces for these distance measures due to the availability of efficient indexing schemes on metric spaces. We provide explicit constructions of point sets under the Bhattacharyya and the Kullback-Leibler divergences whose embeddings into any metric space incur arbitrarily large distortions. We show that the lower bound presented for Bhattacharyya distance is nearly tight by providing an embedding that approaches the lower bound for relatively small dimensional datasets.
Topology of 2D and 3D Rational Curves
Venue: arXiv cs.SC 2009
Year: 2009

In this paper we present algorithms for computing the topology of planar and space rational curves defined by a parametrization. The algorithms given here work directly with the parametrization of the curve, and do not require to compute or use the implicit equation of the curve (in the case of planar curves) or of any projection (in the case of space curves). Moreover, these algorithms have been implemented in Maple; the examples considered and the timings obtained show good performance skills.
Digital Ecosystems
Venue: arXiv cs.MA 2009
Year: 2009

We view Digital Ecosystems to be the digital counterparts of biological ecosystems, which are considered to be robust, self-organising and scalable architectures that can automatically solve complex, dynamic problems. So, this work is concerned with the creation, investigation, and optimisation of Digital Ecosystems, exploiting the self-organising properties of biological ecosystems. First, we created the Digital Ecosystem, a novel optimisation technique inspired by biological ecosystems, where the optimisation works at two levels: a first optimisation, migration of agents which are distributed in a decentralised peer-to-peer network, operating continuously in time; this process feeds a second optimisation based on evolutionary computing that operates locally on single peers and is aimed at finding solutions to satisfy locally relevant constraints. We then investigated its self-organising aspects, starting with an extension to the definition of Physical Complexity to include evolving agent populations. Next, we established stability of evolving agent populations over time, by extending the Chli-DeWilde definition of agent stability to include evolutionary dynamics. Further, we evaluated the diversity of the software agents within evolving agent populations. To conclude, we considered alternative augmentations to optimise and accelerate our Digital Ecosystem, by studying the accelerating effect of a clustering catalyst on the evolutionary dynamics. We also studied the optimising effect of targeted migration on the ecological dynamics, through the indirect and emergent optimisation of the agent migration patterns. Overall, we have advanced the understanding of creating Digital Ecosystems, the self-organisation that occurs within them, and the optimisation of their Ecosystem-Oriented Architecture.
Planet-scale Human Mobility Measurement
Venue: arXiv cs.NI 2009
Year: 2009

Research into, and design and construction of mobile systems and algorithms requires access to large-scale mobility data. Unfortunately, the wireless and mobile research community lacks such data. For instance, the largest available human contact traces contain only 100 nodes with very sparse connectivity, limited by experimental logistics. In this paper we pose a challenge to the community: how can we collect mobility data from billions of human participants? We re-assert the importance of large-scale datasets in communication network design, and claim that this could impact fundamental studies in other academic disciplines. In effect, we argue that planet-scale mobility measurements can help to save the world. For example, through understanding large-scale human mobility, we can track and model and contain the spread of epidemics of various kinds.
Securing Remote Procedure Calls over HTTPS
Venue: arXiv cs.CR 2009
Year: 2009

Remote Procedure Calls (RPC) are widely used over the Internet as they provide a simple and elegant way of interaction between the client and the server. This paper proposes a solution for securing the remote procedure calls (RPC) by tunneling it through HTTPS (Hypertext Transfer Protocol over Secure Socket Layer). RPC over HTTP actually uses the Secure Socket Layer (SSL) protocol as a transport for the traffic. SSL mandates that the server authenticates itself to the client using a digital certificate (and associated private key). SSL is normally configured to encrypt traffic before transmitting it between the server and client and vice versa.