The big data of violent events: algorithms for association analysis using spatio-temporal storytelling

This paper proposes three methods of association analysis that address two challenges of Big Data: capturing relatedness among real-world events in high data volumes, and modeling similar events that are described disparately under high data variability. The proposed methods take as input a set of geotemporally-encoded text streams about violent events called “storylines”. These storylines are associated for two purposes: to investigate if an event could occur again, and to measure influence, i.e., how one event could help explain the occurrence of another. The first proposed method, Distance-based Bayesian Inference, uses spatial distance to relate similar events that are described differently, addressing the challenge of high variability. The second and third methods, Spatial Association Index and Spatio-logical Inference, measure the influence of storylines in different locations, dealing with the high-volume challenge. Extensive experiments on social unrest in Mexico and wars in the Middle East showed that these methods can achieve precision and recall as high as 80 % in retrieval tasks that use both keywords and geospatial information as search criteria. In addition, the experiments demonstrated high effectiveness in uncovering real-world storylines for exploratory analysis.     

Value-based requirements engineering: exploring innovative e-commerce ideas

Innovative e-commerce ideas are characterised by commercial products yet unknown to the market, enabled by information technology such as the Internet and technologies on top of it. How to develop such products is hardly known. We propose an interdisciplinary approach, e ³ -value, to explore an innovative e-commerce idea with the aim of understanding such an idea thoroughly and evaluating it for potential profitability. Our methodology exploits a requirements engineering way of working, but employs concepts and terminology from business science, marketing and axiology. It shows how to model business requirements and improve business–IT alignment, in sophisticated multi-actor value constellations that are common in electronic commerce. In addition to the e ³ -value approach methodology, we also present the action research-based development of our methodology, by using one of the longitudinal projects we carried out in the field of online news article provisioning.     

Semantically-Guided Goal-Sensitive Reasoning: Model Representation

SGGS (Semantically-Guided Goal-Sensitive reasoning) is a clausal theorem-proving method, which generalizes to first-order logic the Davis-Putnam-Loveland-Logemann procedure with conflict-driven clause learning (DPLL-CDCL). SGGS starts from an initial interpretation, and works towards modifying it into a model of a given set of clauses, reporting unsatisfiability if there is no model. The state of the search for a model is described by a structure, called SGGS clause sequence. We present SGGS clause sequences as a formalism to represent models; and we prove their properties related to the mechanisms of SGGS for clausal propagation, conflict solving, and conflict-driven model repair at the first-order level.     

Team formation with influence maximization for influential event organization on social networks

Online event-based social services allow users to organize social events by specifying the themes, and invite friends to participate social events. While the event information can be spread over the social network, it is expected that by certain communication between event hosts, users interested in the event themes can be as more as possible. In this paper, by combining the ideas of team formation and influence maximization, we formulate a novel research problem, Influential Team Formation (ITF), to facilitate the organization of social events. Given a set L of required labels to describe the event topics, a social network, and the size k of the host team, ITF is to find a k-node set S that satisfying L and maximizing the Influence-Cost Ratio (i.e., the influence spread per communication cost between team members). Since ITF is proved to be NP-hard, we develop two greedy algorithms and one heuristic method to solve it. Extensive experiments conducted on Facebook and Google+ datasets exhibit the effectiveness and efficiency of the proposed methods. In addition, by employing the real event participation data in Meetup, we show that ITF with the proposed solutions is able to predict organizers of influential events.     

A computational model of transmedia ecosystem for story-based contents

Story-based contents (e.g., novel, movies, and computer games) have been dynamically transformed into various media. In this environment, the contents are not complete in themselves, but closely connected with each other. Also, they are not simply transformed form a medium to other media, but expanding their stories. It is called as a transmedia storytelling, and a group of contents following it is called as a transmedia ecosystem. Since the contents are highly connected in terms of the story in the transmedia ecosystem, the existing content analysis methods are hard to extract relationships between the contents. Therefore, a proper content analysis method is needed with considering expansions of the story. The aim of this work is to understand how (and why) such contents are transformed by i) defining the main features of the transmedia storytelling and ii) building the taxonomy among the transmedia patterns. More importantly, computational transmedia ecosystem is designed to process a large number of the contents, and to support high understandability of the complex transmedia patterns.     

Bottleneck-aware arrangement over event-based social networks: the max-min approach

With the popularity of mobile computing and social media, various kinds of online event-based social network (EBSN) platforms, such as Meetup, Plancast and Whova, are gaining in prominence. A fundamental task of managing EBSN platforms is to recommend suitable social events to potential users according to the following three factors: spatial locations of events and users, attribute similarities between events and users, and friend relationships among users. However, none of the existing approaches considers all the aforementioned influential factors when they recommend users to proper events. Furthermore, the existing recommendation strategies neglect the bottleneck cases of the global recommendation. Thus, it is impossible for the existing recommendation solutions to be fair in real-world scenarios. In this paper, we first formally define the problem of bottleneck-aware social event arrangement (BSEA), which is proven to be NP-hard. To solve the BSEA problem approximately, we devise two greedy heuristic algorithms, Greedy and Random+Greedy, and a local-search-based optimization technique. In particular, the Greedy algorithm is more effective but less efficient than the Random+Greedy algorithm in most cases. Moreover, a variant of the BSEA problem, called the Extended BSEA problem, is studied, and the above solutions can be extended to address this variant easily. Finally, we conduct extensive experiments on real and synthetic datasets which verify the efficiency and effectiveness of our proposed algorithms.     

Continuous visible nearest neighbor query processing in spatial databases

In this paper, we identify and solve a new type of spatial queries, called continuous visible nearest neighbor (CVNN) search. Given a data set P, an obstacle set O, and a query line segment q in a two-dimensional space, a CVNN query returns a set of \({\langle p, R\rangle}\) tuples such that \({p \in P}\) is the nearest neighbor to every point r along the interval \({R \subseteq q}\) as well as p is visible to r. Note that p may be NULL, meaning that all points in P are invisible to all points in R due to the obstruction of some obstacles in O. In contrast to existing continuous nearest neighbor query, CVNN retrieval considers the impact of obstacles on visibility between objects, which is ignored by most of spatial queries. We formulate the problem, analyze its unique characteristics, and develop efficient algorithms for exact CVNN query processing. Our methods (1) utilize conventional data-partitioning indices (e.g., R-trees) on both P and O, (2) tackle the CVNN search by performing a single query for the entire query line segment, and (3) only access the data points and obstacles relevant to the final query result by employing a suite of effective pruning heuristics. In addition, several interesting variations of CVNN queries have been introduced, and they can be supported by our techniques, which further demonstrates the flexibility of the proposed algorithms. A comprehensive experimental evaluation using both real and synthetic data sets has been conducted to verify the effectiveness of our proposed pruning heuristics and the performance of our proposed algorithms.     

<Emphasis Type="Italic">D</Emphasis>-decomposition technique state-of-the-art

It is a survey of recent extensions and new applications for the classical D-decomposition technique. We investigate the structure of the parameter space decomposition into root invariant regions for single-input single-output systems linear depending on the parameters. The D-decomposition for uncertain polynomials is considered as well as the problem of describing all stabilizing controllers of the certain structure (for instance, PID-controllers) that satisfy given H _∞-criterion. It is shown that the D-decomposition technique can be naturally linked with M-Δ framework (a general scheme for analysis of uncertain systems) and it is applicable for describing feasible sets for linear matrix inequalities. The problem of robust synthesis for linear systems can be also treated via D-decomposition technique.     

Exact and approximate flexible aggregate similarity search

Aggregate similarity search, also known as aggregate nearest-neighbor (Ann) query, finds many useful applications in spatial and multimedia databases. Given a group Q of M query objects, it retrieves from a database the objects most similar to Q, where the similarity is an aggregation (e.g., \({{\mathrm{sum}}}\), \(\max \)) of the distances between each retrieved object p and all the objects in Q. In this paper, we propose an added flexibility to the query definition, where the similarity is an aggregation over the distances between p and any subset of \(\phi M\) objects in Q for some support \(0< \phi \le 1\). We call this new definition flexible aggregate similarity search and accordingly refer to a query as a flexible aggregate nearest-neighbor ( Fann ) query. We present algorithms for answering Fann queries exactly and approximately. Our approximation algorithms are especially appealing, which are simple, highly efficient, and work well in both low and high dimensions. They also return near-optimal answers with guaranteed constant-factor approximations in any dimensions. Extensive experiments on large real and synthetic datasets from 2 to 74 dimensions have demonstrated their superior efficiency and high quality.     

Shadow Prices in Territory Division

We consider a geographic optimization problem in which we are given a region R, a probability density function f(?) defined on R, and a collection of n utility density functions u _i (?) defined on R. Our objective is to divide R into n sub-regions R _i so as to “balance” the overall utilities on the regions, which are given by the integrals \(\iint _{R_{i}}f(x)u_{i}(x)\, dA\). Using a simple complementary slackness argument, we show that (depending on what we mean precisely by “balancing” the utility functions) the boundary curves between optimal sub-regions are level curves of either the difference function u _i (x) ? u _j (x) or the ratio u _i (x)/u _j (x). This allows us to solve the problem of optimally partitioning the region efficiently by reducing it to a low-dimensional convex optimization problem. This result generalizes, and gives very short and constructive proofs of, several existing results in the literature on equitable partitioning for particular forms of f(?) and u _i (?). We next give two economic applications of our results in which we show how to compute a market-clearing price vector in an aggregate demand system or a variation of the classical Fisher exchange market. Finally, we consider a dynamic problem in which the density function f(?) varies over time (simulating population migration or transport of a resource, for example) and derive a set of partial differential equations that describe the evolution of the optimal sub-regions over time. Numerical simulations for both static and dynamic problems confirm that such partitioning problems become tractable when using our methods.     

Using neural networks to integrate structural analysis package and optimization package

To solve structural optimization problems, it is necessary to integrate a structural analysis package and an optimization package. Since most structural analysis packages suffer from closeness of system, it is very difficult to integrate it with an optimization package. To overcome the difficulty, we propose a possible alternative, DAMDO, which integrate Design, Analysis, Modeling, Definition, and Optimization phases into an integration environment as follows. (1) Design first generate many possible structural design alternatives. Each design alternative consists of many design variables X. (2) Analysis employ the structural analysis software to analyze all structural design alternatives to obtain their internal forces and displacements. They are the response variables Y. (3) Modeling employ artificial neural networks to build model Y = f(X) to obtain the relationship functions between the design variables X and the response variables Y. (4) Definition employ the design variables X and the response variables Y to define the objective function and constraint functions. (5) Optimization employ the optimization software to solve the optimization problem consisting of the objective function and the constraint functions to produce the optimum design variables X*. Optimization of truss structures was used to validate the DAMDO approach. The empirical results show that the truss optimization problems can be solved by the DAMDO approach, which employ neural networks to integrate the structural analysis package and optimization package without requiring direct integration of the two packages. This approach is promising in many engineering optimization domains which need to couple an analysis package and an optimization one to obtain the optimum solutions.     

Asymptotic confidence interval for conditional probability at decision making

Consideration was given to construction of a unilateral asymptotic confidence interval for an unknown conditional probability of the event A under the condition B. Analytical expressions for the boundaries of such interval were obtained for various a priori restrictions on the probabilities of the events A and B such that the probability of the event B is separable from zero by a certain value, as well that there exists an upper a priori restriction on the probability of the event A. The interval estimates obtained were compared in precision.     

High order stable infinite impulse response filter design using cuckoo search algorithm

In this paper, an efficient technique for optimal design of digital infinite impulse response (IIR) filter with minimum passband error (e _p ), minimum stopband error (e _s ), high stopband attenuation (A _s ), and also free from limit cycle effect is proposed using cuckoo search (CS) algorithm. In the proposed method, error function, which is multi-model and non-differentiable in the heuristic surface, is constructed as the mean squared difference between the designed and desired response in frequency domain, and is optimized using CS algorithm. Computational efficiency of the proposed technique for exploration in search space is examined, and during exploration, stability of filter is maintained by considering lattice representation of the denominator polynomials, which requires less computational complexity as well as it improves the exploration ability in search space for designing higher filter taps. A comparative study of the proposed method with other algorithms is made, and the obtained results show that 90% reduction in errors is achieved using the proposed method. However, computational complexity in term of CPU time is increased as compared to other existing algorithms.     

A query refinement framework for xml keyword search

Existing work of XML keyword search focus on how to find relevant and meaningful data fragments for a query, assuming each keyword is intended as part of it. However, in XML keyword search, user queries usually contain irrelevant or mismatched terms, typos etc, which may easily lead to empty or meaningless results. In this paper, we introduce the problem of content-aware XML keyword query refinement, where the search engine should judiciously decide whether a user query Q needs to be refined during the processing of Q, and find a list of promising refined query candidates which guarantee to have meaningful matching results over the XML data, without any user interaction or a second try. To achieve this goal, we build a novel content-aware XML keyword query refinement framework consisting of two core parts: (1) we build a query ranking model to evaluate the quality of a refined query RQ, which captures the morphological/semantical similarity between Q and RQ and the dependency of keywords of RQ over the XML data; (2) we integrate the exploration of RQ candidates and the generation of their matching results as a single problem, which is fulfilled within a one-time scan of the related keyword inverted lists optimally. Finally, an extensive empirical study verifies the efficiency and effectiveness of our framework.     

Patent Protection in a Model of Economic Growth in Multiple Regions

We study the effects of patent protection on economic growth in the ith region when this ith region is part of an aggregate economy of i?=?1,…,N regions. The regulatory authority in the ith region attempts to curtail the monopoly power of patent holding input producers by requiring them to charge a price that is parametrically related to the unconstrained monopoly price. Our analysis generates three results. First, we show the manner in which the equilibrium growth rate of the ith region is related to the above mentioned parameter. Second, we demonstrate the impact that changes in the stringency of patent protection have on the ith region’s equilibrium growth rate. Finally, we explain why eliminating the monopoly distortion does not maximize social welfare in the ith region.     

A new strategy for generating shortest addition sequences

An addition sequence problem is given a set of numbers X = {n ₁, n ₂, . . . , n _m }, what is the minimal number of additions needed to compute all m numbers starting from 1? This problem is NP-complete. In this paper, we present a branch and bound algorithm to generate an addition sequence with a minimal number of elements for a set X by using a new strategy. Then we improve the generation by generalizing some results on addition chains (m = 1) to addition sequences and finding what we will call a presumed upper bound for each n _j , 1 ≤ j ≤ m, in the search tree.     

On Fixed Cost k-Flow Problems

In the Fixed Cost k-Flow problem, we are given a graph G = (V, E) with edge-capacities {u _e ∣e ∈ E} and edge-costs {c _e ∣e ∈ E}, source-sink pair s, t ∈ V, and an integer k. The goal is to find a minimum cost subgraph H of G such that the minimum capacity of an st-cut in H is at least k. By an approximation-preserving reduction from Group Steiner Tree problem to Fixed Cost k-Flow, we obtain the first polylogarithmic lower bound for the problem; this also implies the first non-constant lower bounds for the Capacitated Steiner Network and Capacitated Multicommodity Flow problems. We then consider two special cases of Fixed Cost k-Flow. In the Bipartite Fixed-Cost k-Flow problem, we are given a bipartite graph G = (A ∪ B, E) and an integer k > 0. The goal is to find a node subset S ? A ∪ B of minimum size |S| such G has k pairwise edge-disjoint paths between S ∩ A and S ∩ B. We give an \(O(\sqrt {k\log k})\) approximation for this problem. We also show that we can compute a solution of optimum size with Ω(k/polylog(n)) paths, where n = |A| + |B|. In the Generalized-P2P problem we are given an undirected graph G = (V, E) with edge-costs and integer charges {b _v : v ∈ V}. The goal is to find a minimum-cost spanning subgraph H of G such that every connected component of H has non-negative charge. This problem originated in a practical project for shift design [11]. Besides that, it generalizes many problems such as Steiner Forest, k-Steiner Tree, and Point to Point Connection. We give a logarithmic approximation algorithm for this problem. Finally, we consider a related problem called Connected Rent or Buy Multicommodity Flow and give a log^3+?? n approximation scheme for it using Group Steiner Tree techniques.     

Optimizing top-<Emphasis Type="Italic">k</Emphasis> retrieval: submodularity analysis and search strategies

The key issue in top-k retrieval, finding a set of k documents (from a large document collection) that can best answer a user’s query, is to strike the optimal balance between relevance and diversity. In this paper, we study the top-k retrieval problem in the framework of facility location analysis and prove the submodularity of that objective function which provides a theoretical approximation guarantee of factor 1?\(\frac{1}{e}\) for the (best-first) greedy search algorithm. Furthermore, we propose a two-stage hybrid search strategy which first obtains a high-quality initial set of top-k documents via greedy search, and then refines that result set iteratively via local search. Experiments on two large TREC benchmark datasets show that our two-stage hybrid search strategy approach can supersede the existing ones effectively and efficiently.     

Indefinite summation of rational functions with additional minimization of the summable part

An algorithm of indefinite summation of rational functions is proposed. For a given function f(x), it constructs a pair of rational functions g(x) and r(x) such that f(x) = g(x + 1) ? g(x) + r(x), where the degree of the denominator of r(x) is minimal, and, when this condition is satisfied, the degree of the denominator of g(x) is also minimal.     

Cryptanalysis of an MOR cryptosystem based on a finite associative algebra基于有限结合代数的 MOR 公钥密码安全性分析

The Shor algorithm is effective for public-key cryptosystems based on an abelian group. At CRYPTO 2001, Paeng (2001) presented a MOR cryptosystem using a non-abelian group, which can be considered as a candidate scheme for post-quantum attack. This paper analyses the security of a MOR cryptosystem based on a finite associative algebra using a quantum algorithm. Specifically, let L be a finite associative algebra over a finite field F. Consider a homomorphism φ: Aut(L) → Aut(H)×Aut(I), where I is an ideal of L and H ? L/I. We compute dim Im(φ) and dim Ker(φ), and combine them by dim Aut(L) = dim Im(φ)+dim Ker(φ). We prove that Im(φ) = Stab_Comp(H,I)(μ + B²(H, I)) and Ker(φ) ? Z¹(H, I). Thus, we can obtain dim Im(φ), since the algorithm for the stabilizer is a standard algorithm among abelian hidden subgroup algorithms. In addition, Z¹(H, I) is equivalent to the solution space of the linear equation group over the Galois fields GF(p), and it is possible to obtain dim Ker(φ) by the enumeration theorem. Furthermore, we can obtain the dimension of the automorphism group Aut(L). When the map ? ∈ Aut(L), it is possible to effectively compute the cyclic group 〈?〉 and recover the private key a. Therefore, the MOR scheme is insecure when based on a finite associative algebra in quantum computation.