On probabilistic n-ary hypergroups

The T-fuzzy n-ary subhypergroups of an n-ary hypergroup are defined by using triangular norms and some related properties are hence obtained. In particular, we consider the probabilistic version of n-ary hypergroups by using random sets and show that the fuzzy n-ary hypergroups defined by triangular norms are consequences of some probabilistic n-ary hypergroups under certain conditions. Some results on n-ary hypergroups recently given by Davvaz and Corsini are extended.     

Augmented k-ary n-cubes

We define an interconnection network AQ_n,k which we call the augmented k-ary n-cube by extending a k-ary n-cube in a manner analogous to the existing extension of an n-dimensional hypercube to an n-dimensional augmented cube. We prove that the augmented k-ary n-cube AQ_n,k has a number of attractive properties (in the context of parallel computing). For example, we show that the augmented k-ary n-cube AQ_n,k: is a Cayley graph, and so is vertex-symmetric, but not edge-symmetric unless n = 2; has connectivity 4n − 2 and wide-diameter at most max{(n − 1)k − (n − 2), k + 7}; has diameter , when n = 2; and has diameter at most , for n ? 3 and k even, and at most , for n ? 3 and k odd.     

The rotation graph of k-ary trees is Hamiltonian

In this paper we show that the graph of k-ary trees, connected by rotations, contains a Hamilton cycle. Our proof is constructive and thus provides a cyclic Gray code for k-ary trees. Furthermore, we identify a basic building block of this graph as the 1-skeleton of the polytopal complex dual to the lower faces of a certain cyclic polytope.     

Upper bounds on the queuenumber of k-ary n-cubes

A queue layout of a graph consists of a linear order of its vertices, and a partition of its edges into queues, such that no two edges in the same queue are nested. The minimum number of queues in a queue layout of a graph G, denoted by qn(G), is called the queuenumber of G. Heath and Rosenberg [SIAM J. Comput. 21 (1992) 927-958] showed that boolean n-cube (i.e., the n-dimensional hypercube) can be laid out using at most n−1 queues. Heath et al. [SIAM J. Discrete Math. 5 (1992) 398-412] showed that the ternary n-cube can be laid out using at most 2n−2 queues. Recently, Hasunuma and Hirota [Inform. Process. Lett. 104 (2007) 41-44] improved the upper bound on queuenumber to n−2 for hypercubes. In this paper, we deal with the upper bound on queuenumber of a wider class of graphs called k-ary n-cubes, which contains hypercubes and ternary n-cubes as subclasses. Our result improves the previous bound in the case of ternary n-cubes. Let denote the n-dimensional k-ary cube. This paper contributes three main results as follows:

(1)

if n?3.

(2)

if n?2 and 4?k?8.

(3)

if n?1 and k?9.

     

On the linear complexity of some new q-ary sequences

Some new q-ary sequences with period q^3ek-1 (q=p^m, p an odd prime, m, e, k integers) are first constructed and then, inspired by Antweiler’s method, their linear complexity is examined. The exact value of linear complexity k(6e)^w is determined when . Furthermore, an upper bound of the linear complexity is given for the other values of r. Our results show that this sequence has larger linear span than GMW sequence with the same parameters. Finally, the results of a Maple program are included to illustrate the validity of the results.     

New bounds on D-ary optimal codes

We propose a simple method that, given a symbol distribution, yields upper and lower bounds on the average code length of a D-ary optimal code over that distribution. Thanks to its simplicity, the method permits deriving analytical bounds for families of parametric distributions. We demonstrate this by obtaining new bounds, much better than the existing ones, for Zipf and exponential distributions when D>2.     

Computing (r, Q) policy for an inventory system with limited sharable resource

This paper deals with inventory systems with limited resource for a single item or multiple items under continuous review (r, Q) policies. For the single-item system with a stochastic demand and limited resource, it is shown that an existing algorithm can be applied to find an optimal (r, Q) policy that minimizes the expected system costs. For the multi-item system with stochastic demands and limited resource commonly shared among all items, an optimization problem is formulated for finding optimal (r, Q) policies for all items, which minimize the expected system costs. Bounds on the parameters (i.e., r and Q) of the optimal policies and bounds on the minimum expected system costs are obtained. Based on the bounds, an algorithm is developed for finding an optimal or near-optimal solution. A method is proposed for evaluating the quality of the solution. It is shown that the algorithm proposed in this paper finds a solution that is (i) optimal/near-optimal and/or (ii) significantly better than the optimal solution with unlimited resource.     

Pricing and inventory management in a system with multiple competing retailers under (r, Q) policies

We consider a multi-retailer system operated on an infinite horizon, in which each retailer faces stochastic demand following a Poisson process and adopts a continuous-review (r, Q) policy for replenishing inventory to satisfy customer demand. The system involves decisions of pricing and inventory management with the goal of maximizing profit, which equals the sales revenue minus the purchase and inventory costs. Taking Cournot competition into account, models are formulated to optimize simultaneously the expected sales volumes and (r, Q) policies of all retailers. An efficient approach is proposed to calculate the approximate inventory cost. Based on this approach, solution methods for centralized and decentralized scenarios are developed. A great number of numerical computations are provided to evaluate the efficiency of the solution methods, and their performance in the two scenarios. Moreover, system performance under sequential decisions (first pricing and then inventory management) is also investigated.     

Edge-bipancyclicity of the k-ary n-cubes with faulty nodes and edges

The k-ary n-cube has been one of the most popular interconnection networks for massively parallel systems. In this paper, we investigate the edge-bipancyclicity of k-ary n-cubes with faulty nodes and edges. It is proved that every healthy edge of the faulty k-ary n-cube with f_v faulty nodes and f_e faulty edges lies in a fault-free cycle of every even length from 4 to kⁿ − 2f_v (resp. kⁿ − f_v) if k ? 4 is even (resp. k ? 3 is odd) and f_v + f_e ? 2n − 3. The results are optimal with respect to the number of node and edge faults tolerated.     

Hamiltonian circuit and linear array embeddings in faulty k-ary n-cubes

In this paper, we investigate the fault-tolerant capabilities of the k-ary n-cubes for even integer k with respect to the hamiltonian and hamiltonian-connected properties. The k-ary n-cube is a bipartite graph if and only if k is an even integer. Let F   be a faulty set with nodes and/or links, and let k?3$k?3$ be an odd integer. When |F|?2n-2$\left|F\right|?2n-2$, we show that there exists a hamiltonian cycle in a wounded k-ary n  -cube. In addition, when |F|?2n-3$\left|F\right|?2n-3$, we prove that, for two arbitrary nodes, there exists a hamiltonian path connecting these two nodes in a wounded k-ary n-cube. Since the k-ary n  -cube is regular of degree 2n$2n$, the degrees of fault-tolerance 2n-3$2n-3$ and 2n-2$2n-2$ respectively, are optimal in the worst case.     

Countering overlapping rectangle privacy attack for moving kNN queries

An important class of LBSs is supported by the moving k nearest neighbor (MkNN) query, which continuously returns the k nearest data objects for a moving user. For example, a tourist may want to observe the five nearest restaurants continuously while exploring a city so that she can drop in to one of them anytime. Using this kind of services requires the user to disclose her location continuously and therefore may cause privacy leaks derived from the user's locations. A common approach to protecting a user's location privacy is the use of imprecise locations (e.g., regions) instead of exact positions when requesting LBSs. However, simply updating a user's imprecise location to a location-based service provider (LSP) cannot ensure a user's privacy for an MkNN query: continuous disclosure of regions enable LSPs to refine more precise location of the user. We formulate this type of attack to a user's location privacy that arises from overlapping consecutive regions, and provide the first solution to counter this attack. Specifically, we develop algorithms which can process an MkNN query while protecting the user's privacy from the above attack. Extensive experiments validate the effectiveness of our privacy protection technique and the efficiency of our algorithm.     

Partial match queries in relaxed multidimensional search trees

Partial match queries arise frequently in the context of large databases, where each record contains a distinct multidimensional key, that is, the key of each record is aK-tuple of values. The components of a key are called thecoordinates orattributes of the key. In a partial match query we specify the value ofs attributes, 0<s<K, and leave the remainingK —s attributes unspecified. The goal is to retrieve all the records in the database that match the specified attributes. In this paper we present several results about the average performance and variance of partial matches in relaxedK-dimensional trees (search trees and digital tries). These data structures are variants of the well knownK d-trees andK d-tries. In relaxed trees the sequence of attributes used to guide a query is explicitly stored at the nodes of the tree and randomly generated and, in general, will be different for different search paths. In the standard variants, the sequence of attributes that guides a query examines the attributes in a cyclic fashion, fixed and identical for all search paths. We show that the probabilistic analysis of the relaxed multidimensional trees is very similar to that of standardK d-trees andK d-tries, and also to the analysis of quadtrees. In fact, besides the average cost and variance of partial match in relaxedK d-trees andK d-tries, we also obtain the variance of partial matches in two-dimensional quadtrees. We also compute the average cost of partial matches in other relaxed multidimensional digital tries, namely, relaxedK d-Patricia and relaxedK d-digital search trees. This research was supported by Acciones Integradas Hispano-Austríacas HU1997-0016 (Austrian-Spanish Scientific Exchange Program). The first author was also supported by ESPRIT LTR 20244 (ALCOM IT), CICYT TIC97-1475-CE, DGES PB95-0787 (KOALA), and CIRIT 1997SGR-00366 (SGR). The second author was also supported by the Austrian Research Society (FWF) under Project P12599-MAT. Online publication October 13, 2000.     

Vague continuous K-nearest neighbor queries over moving objects with uncertain velocity in road networks

Recent research has focused on Continuous K Nearest Neighbor (CKNN) queries in road networks, where the queries and the data objects are moving. Most existing approaches assume the fixed velocity of moving objects. The release of fixed moving velocity makes the query process slowly due to the significant repetitive query cost. In this paper, we study CKNN queries over moving objects with uncertain velocity in road networks. A Distance Interval Model (DIM) is designed to calculate the minimal and maximal road network distances between moving objects and query point. Furthermore, we propose a novel Possibility-based Vague KNN (PVKNN) algorithm to process the query efficiently, which determines the CKNN query results with possibility within each division time subinterval of given time interval by applying the vague set theory. In the PVKNN algorithm, the query efficiency can be improved significantly with the pruning, distilling and possibility-ranking phases. With these phases, the objects candidates are scaled down and the given time interval is divided into subintervals to reduce the repetitive query cost. In addition, an index structure TPR^uv-Tree is designed to efficiently index moving objects with uncertain velocity in road network by involving edge connection and moving objects information. Experiments with simulation and comparison show that significant improvement in the performance of efficiency can be achieved with our proposed algorithms.     

Applications of interval valued t-norms (t-conorms) to fuzzy n-ary sub-hypergroups

In this paper, we study a generalization of group, hypergroup and n-ary group. Firstly, we define interval-valued fuzzy (anti fuzzy) n-ary sub-hypergroup with respect to a t-norm T (t-conorm S). We give a necessary and sufficient condition for, an interval-valued fuzzy subset to be an interval-valued fuzzy (anti fuzzy) n-ary sub-hypergroup with respect to a t-norm T (t-conorm S). Secondly, using the notion of image (anti image) and inverse image of a homomorphism, some new properties of interval-valued fuzzy (anti fuzzy) n-ary sub-hypergroup are obtained with respect to infinitely ∨-distributive t-norms T (∧-distributive t-conorms S). Also, we obtain some results of T-product (S-product) of the interval-valued fuzzy subsets for infinitely ∨-distributive t-norms T (∧-distributive t-conorms S). Lastly, we investigate some properties of interval-valued fuzzy subsets of the fundamental n-ary group with infinitely ∨-distributive t-norms T (∧-distributive t-conorms S).     

A new type of fuzzy n-ary hyperstructures

The aim of this paper is to consider and study a new kind of fuzzy n-ary hyperstructures, such as fuzzy n-ary hypergroups and fuzzy (m,n)-ary hyperrings.     

Exact k-NN queries on clustered SVD datasets

Clustered SVD-CSVD, which combines clustering and singular value decomposition (SVD), outperforms SVD applied globally, without first applying clustering. Datasets of feature vectors in various application domains exhibit local correlations, which allow CSVD to attain a higher dimensionality reduction than SVD for the same normalized mean square error. We specify an exact method for processing k-nearest-neighbor queries for CSVD, which ensures 100% recall and is experimentally shown to require less CPU processing time than the approximate method originally specified for CSVD.     

Fast exact k nearest neighbors search using an orthogonal search tree

The problem of k nearest neighbors (kNN) is to find the nearest k neighbors for a query point from a given data set. In this paper, a novel fast kNN search method using an orthogonal search tree is proposed. The proposed method creates an orthogonal search tree for a data set using an orthonormal basis evaluated from the data set. To find the kNN for a query point from the data set, projection values of the query point onto orthogonal vectors in the orthonormal basis and a node elimination inequality are applied for pruning unlikely nodes. For a node, which cannot be deleted, a point elimination inequality is further used to reject impossible data points. Experimental results show that the proposed method has good performance on finding kNN for query points and always requires less computation time than available kNN search algorithms, especially for a data set with a big number of data points or a large standard deviation.     

Atanassov’s intuitionistic (S, T)-fuzzy n-ary sub-hypergroups and their properties

In this paper, we define a new kind of intuitionistic fuzzy n-ary sub-hypergroups of an n-ary hypergroup. This definition, which is based on Atanassov’s intuitionistic fuzzy sets, t-norms and t-conorms, includes earlier definitions of (n-ary) sub-hypergroups, (intuitionistic) fuzzy (n-ary) sub-hypergroups. Then some related properties are investigated. Also, intuitionistic fuzzy relations with respect to t-norms and t-conorms on n-ary hypergroups are discussed.     

The partitioned-layer index: Answering monotone top-k queries using the convex skyline and partitioning-merging technique

A top-k query returns k tuples with the highest (or the lowest) scores from a relation. The score is computed by combining the values of one or more attributes. We focus on top-k queries having monotone linear score functions. Layer-based methods are well-known techniques for top-k query processing. These methods construct a database as a single list of layers. Here, the ith layer has the tuples that can be the top-i tuple. Thus, these methods answer top-k queries by reading at most k layers. Query performance, however, is poor when the number of tuples in each layer (simply, the layer size) is large. In this paper, we propose a new layer-ordering method, called the Partitioned-Layer Index (simply, the PL Index), that significantly improves query performance by reducing the layer size. The PL Index uses the notion of partitioning, which constructs a database as multiple sublayer lists instead of a single layer list subsequently reducing the layer size. The PL Index also uses the convex skyline, which is a subset of the skyline, to construct a sublayer to further reduce the layer size. The PL Index has the following desired properties. The query performance of the PL Index is quite insensitive to the weights of attributes (called the preference vector) of the score function and is approximately linear in the value of k. The PL Index is capable of tuning query performance for the most frequently used value of k by controlling the number of sublayer lists. Experimental results using synthetic and real data sets show that the query performance of the PL Index significantly outperforms existing methods except for small values of k (say, k?9).     

Selectivity-sensitive shared evaluation of multiple continuous XPath queries over XML streams

One of the primary issues confronting XML message brokers is the difficulty associated with processing a large set of continuous XPath queries over incoming XML streams. This paper proposes a novel system designed to present an effective solution to this problem. The proposed system transforms multiple XPath queries before their run-time into a new data structure, called an XP-table, by sharing their common constraints. An XP-table is matched with a stream relation (SR) transformed from a target XML stream by a SAX parser. This arrangement is intended to minimize the run-time workload of continuous query processing. In addition, an early-query-termination strategy is proposed as an improved alternative to the basic approach. It optimizes query processing by arranging the evaluation sequence of the member-lists (m-lists) of an XP-table adaptively and offers increased efficiency, especially in cases of low selectivity. System performance is estimated and verified through a variety of experiments, including comparisons with previous approaches such as YFilter and LazyDFA. The proposed system is practically linear-scalable and stable for evaluating a set of XPath queries in a continuous and timely fashion.