nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Trajectory Comparison in a Vehicular Network II: Eliminating the Redundancy

verfasst von : Letu Qingge, Peng Zou, Lihui Dai, Qing Yang, Binhai Zhu

Erschienen in: Wireless Algorithms, Systems, and Applications

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This paper investigates the truthfulness establishment problem between two nodes (vehicles) in a vehicular network. We focus more on the case when no interaction has been conducted and we use the Point of Interests (POIs) visited by the two nodes (vehicles) to establish the initial truthfulness. It turns out that this is a general version of a well-studied problem in computational genomics called CMSR (Complementary Maximal Strip Recovery) in which the letters (similar to POIs) cannot be duplicated, while in our problem POIs could certainly be duplicated. We show that one version (when noisy POIs are deleted all the remaining POIs must be involved in some adjacency), is NP-hard; while the other version (with the adjacency involvement constraint is dropped), is as hard as Set Cover. We then design a practical solution based on local search for the first problem. Simulations with various synthetic data show that the algorithm is very effective.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel An Efficient and Recoverable Data Sharing Mechanism for Edge Storage

Nächstes Kapitel Differentially Private Event Sequences over Infinite Streams with Relaxed Privacy Guarantee

Angibaud, S., Fertin, G., Rusu, I., Thevenin, A., Vialette, S.: On the approximability of comparing genomes with duplicates. J. Graph Algorithms Appl. 13(1), 19–53 (2009)

Bar-Yehuda, R., Halldórsson, M.M., Naor, J.S., Shachnai, H., Shapira, I.: Scheduling split intervals. SIAM J. Comput. 36, 1–15 (2006)

Bulteau, L., Fertin, G., Rusu, I.: Maximal strip recovery problem with gaps: hardness and approximation algorithms. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol. 5878, pp. 710–719. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10631-6_72

Chen, Z., Fu, B., Jiang, M., Zhu, B.: On recovering syntenic blocks from comparative maps. J. Comb. Optim. 18, 307–318 (2009)

Choi, V., Zheng, C., Zhu, Q., Sankoff, D.: Algorithms for the extraction of synteny blocks from comparative maps. In: Giancarlo, R., Hannenhalli, S. (eds.) WABI 2007. LNCS, vol. 4645, pp. 277–288. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74126-8_26

Jiang, H., Li, Z., Lin, G., Wang, L., Zhu, B.: Exact and approximation algorithms for the complementary maximal strip recovery problem. J. Comb. Optim. 23(4), 493–506 (2012)

Jiang, H., Zhong, F., Zhu, B.: Filling scaffolds with gene repetitions: maximizing the number of adjacencies. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol. 6661, pp. 55–64. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-21458-5_7

Jiang, H., Zheng, C., Sankoff, D., Zhu, B.: Scaffold filling under the breakpoint and related distances. IEEE/ACM Trans. Comput. Biol. Bioinform. 9(4), 1220–1229 (2012)

Jiang, H., Guo, J., Zhu, D., Zhu, B.: A 2-approximation algorithm for the complementary maximal strip recovery problem. In: Proceedings of the 30th Annual Combinatorial Pattern Matching Symposium (CPM 2019), LIPIcs, vol. 128, pp. 5:1–5:13 (2019)

10.

Jiang, M.: Inapproximability of maximal strip recovery. Theor. Comput. Sci. 412(29), 3759–3774 (2011)

11.

Lin, G., Goebel, R., Li, Z., Wang, L.: An improved approximation algorithm for the complementary maximal strip recovery problem. J. Comput. Syst. Sci. 78(3), 720–730 (2012)

12.

Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and sub-constant error-probability PCP characterization of NP. In: Proceedings of the 29th ACM Symposium on Theory of Computing (STOC 1997), pp. 475–484 (1997)

13.

Shrestha, R., Nam, S.Y.: Trustworthy event-information dissemination in vehicular ad hoc networks. Mobile Inf. Syst. 9050787, 1–16 (2017)

14.

Douceur, J.R.: The sybil attack. In: Druschel, P., Kaashoek, F., Rowstron, A. (eds.) IPTPS 2002. LNCS, vol. 2429, pp. 251–260. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45748-8_24

15.

Hartenstein, H., Kenneth, L.: VANET: Vehicular Applications and Inter-networking Technologies. Wiley, Hoboken (2009)

16.

Papadimitratos, P., et al.: Secure vehicular communication systems: design and architecture. IEEE Commun. Mag. 46(11), 100–109 (2008)

17.

Liu, G., Yang, Q., Wang, H., Lin, X., Wittie, M.: Assessment of multi-hop interpersonal trust in social networks by three-valued subjective logic. In: Proceedings of the INFOCOM 2014, pp. 1698–1706 (2014)

18.

Liu, G., Chen, Q., Yang, Q., Zhu, B., Wang, H., Wang, W.: OpinionWalk: an efficient solution to massive trust assessment in online social networks. In: Proceedings of the INFOCOM 2017, pp. 1–9 (2017)

19.

Shrestha, R., Djuraev, S., Nam, S.Y.: Sybil attack detection in vehicular network based on received signal strength. In: Proceedings of the 3rd International Conference on Connected Vehicles and Expo (ICCVE 2014), pp. 745–746 (2014)

20.

Zhang, J.: A survey on trust management for VANETS. In: Proceedings of 2011 IEEE International Conference on Advanced Information Networking and Applications (AINA 2011), pp. 105–115 (2011)

21.

Wang, L., Zhu, B.: On the tractability of maximal strip recovery. J. Comput. Biol. 17(7), 907–914 (2010)

22.

Zheng, C., Zhu, Q., Sankoff, D.: Removing noise and ambiguities from comparative maps in rearrangement analysis. IEEE/ACM Trans. Comput. Biol. Bioinform. 4, 515–522 (2007)

Titel: Trajectory Comparison in a Vehicular Network II: Eliminating the Redundancy
verfasst von: Letu Qingge
Peng Zou
Lihui Dai
Qing Yang
Binhai Zhu
Verlag: Springer International Publishing
Buch: Wireless Algorithms, Systems, and Applications
Print ISBN: 978-3-030-23596-3

Electronic ISBN: 978-3-030-23597-0

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-23597-0_21

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner